Презентация на тему Конечные автоматы. (Лекция 5)

дальнейшем, если особо не оговорено, под регулярной грамматикой будем

понимать леволинейную грамматику.
Напомним, что грамматика G = (VT, VN, P, S) называется леволинейной, если каждое правило из Р имеет вид A → Bt либо A → t, где A ∈ VN, B ∈ VN, t ∈ VT.

Соглашение: предположим, что анализируемая цепочка заканчивается специальным символом ⊥ - признаком конца цепочки.

a1a2...an⊥ языку грамматики)
первый символ исходной цепочки a1a2...an⊥ заменяем нетерминалом

A, для которого в грамматике есть правило вывода A → a1 ("свертка" терминала a1 к нетерминалу A)
многократно (до тех пор, пока не считаем признак конца) выполняем: полученный на предыдущем шаге нетерминал A и расположенный непосредственно справа от него очередной терминал ai исходной цепочки заменяем нетерминалом B, для которого есть правило вывода B → Aai (i = 2, 3,.., n);

Это эквивалентно построению дерева разбора методом "снизу-вверх": на каждом шаге алгоритма строим один из уровней в дереве разбора, "поднимаясь" от листьев к корню.

на последнем шаге свертка произошла к символу S. ⇒

a1a2...an⊥ ∈ L(G).
прочитана вся цепочка; на последнем шаге свертка произошла к символу, отличному от S. ⇒ a1a2...an⊥ ∉ L(G).
на некотором шаге не нашлось нужной свертки, т.е. для нетерминала A и очередного терминала ai исходной цепочки не нашлось нетерминала B, для которого было бы правило вывода B → Aai. ⇒ a1a2...an⊥ ∉ L(G).
на некотором шаге работы алгоритма оказалось, что есть более одной подходящей свертки. Это говорит о недетерминированности разбора.

(для каждого нетерминала - одну вершину), и еще одну

вершину, помеченную символом, отличным от нетерминальных (например, H).
Эти вершины будем называть состояниями. H - начальное состояние.
соединяем эти состояния дугами по правилам:
для каждого правила грамматики вида W → t соединяем дугой состояния H и W (от H к W) и помечаем дугу символом t;
для каждого правила W → Vt соединяем дугой состояния V и W (от V к W) и помечаем дугу символом t;

это пятерка (K, VT, F, H, S), где
K -

конечное множество состояний;
VT - конечное множество допустимых входных символов;
F - отображение множества K × VT → K, определяющее поведение автомата; F - функция переходов;
H ∈ K - начальное состояние;
S ∈ K - заключительное состояние (либо конечное множество заключительных состояний).
F(A, t) = B означает, что из состояния A по символу t автомат переходит в состояние B.

{S,A,B}, P, S), где P: S → A⊥ A → a |

Bb B → b | Bb разбор будет недетерминированным (т.к. у нетерминалов A и B есть одинаковые правые части - Bb).

Такой грамматике будет соответствовать недетерминированный конечный автомат.

- это пятерка (K, VT, F, H, S), где
K

- конечное множество состояний;
VT - конечное множество допустимых входных символов;
F - отображение множества K × VT в множество подмножеств K;
H ⊂ K - конечное множество начальных состояний;
S ⊂ K - конечное множество заключительных состояний.