2. Переход от праволинейной грамматики к автоматной

Автоматные грамматики, или иначе А-грамматики, имеют правила вывода вида

U::=T или U::=TW, где TV_T; UV_n; WV_n.

Перейти от полученной праволинейной грамматики к автоматной можно расширением нетерминального словаря следующим образом : Sc₁S₁ ; S₁c₂S₂ ; S₂с₃А и т. д., оставляя в правой части правила один терминальный и один нетерминальный символы или один терминальный.

Выполним преобразование праволинейной грамматики G=(V_N, V_T, S, R) в автоматную G"=(V_N", V_T, S, R").

При этом получим следующее множества R правил вывода

Sx7S1;	S1x1S2;	S2x0A;
Sx7S3;	S3x6S4;	S4x2B;
Sx7C;	Sx4F;	Ax5D;
Ax2;	Bx5E;	Bx2;
Cx5E;	Cx2;	Dx3S;
Dx7;	Ex3S;	Ex7;
Fx5F1;	F1x4F2;	F2x0F3;
F3x5;	Fx2F4;	F4x4F5;
F5x0F6;	F6x5;	Fx1F7.
F7x4F8;	F8x5;

Следовательно, словарь нетерминальных символов V_N будет иметь вид

V"_N = {S, S₁ , S₂, S₃, S₄, А, В, С, D, E, F, F₁, F₂, F₃, F₄, F₅, F₆, F₇, F₈,}.

В рассматриваемом примере нетерминальный словарь имеет 19 символов и его мощность V"_N равна 19, мощность V_T  терминального словаря V_T равна 8.

3. Построение недетерминированного конечного автомата

Недетерминированный конечный автомат — это пятерка

A=(Q, V, М, S, Z), где

Q - множество (алфавит) внутренних состояний;

V - входной алфавит;

М — функция переходов, представляющая отображение

V*Q P(Q);

P(Q) — множество подмножеств из Q;

S Q — множество начальных состояний;

Z  Q — множество заключительных состояний;

SZ.

Недетерминированный конечный автомат (в отличие от детерминированного) может иметь несколько начальных состояний. Отличается он и функциями перехода.

Как правило, недетерминированные конечные автоматы порождаются регулярными грамматиками, которые содержат правила вывода вида

U::= TW R::= TW,

Частичная функция переходов этого случая имеет вид:

M(W,T)={U,R}.

В рассматриваемом примере недетерминированный конечный автомат имеет одно начальное состояние S. Зададим этот автомат следующим образом. Поставим в соответствие символам нетерминального словаря V"_N состояния из Q , в том числе нетерминалу S — начальное состояние q_o . Добавим заключительное состояние Z, в котором автомат оказывается, если цепочка символов, поступающих на автомат, принадлежит L (G").

Составим табл. 3, в которой нетерминальным символам из множества V"_N соответствуют состояния автомата из множества Q.

Таблица 3

S	S1	S2	S3	S4	A	В	С	D	E
qo	q1	q2	q3	q4	q5	q6	q7	q8	q9
F	F1	F2	F3	F4	F5	F6	F7	F8	Z
q10	q11	q12	q13	q14	q15	q16	q17	q18	q19

Здесь начальному состоянию S соответствует q_o, конечному Z - q₁₉.

Общее количество состояний Q = V "_N +1 и равно 20.

Поставим в соответствие правилам вывода переходы автомата.

Так, правилу Аx₁D - переход из состояния q₅ в состояние q₈ под воздействием входного символа x₁, а правилу Ех₇ — переход из состояния q₉ в заключительное состояние q₁₉ при входном символе х₇.

Выполнив указанные действия для всех правил R", получаем таблицу переходов (табл. 4) недетерминированного конечного автомата, соответствующего рассматриваемому примеру. Граф переходов, построенный по этой таблице, приведен на рис.1.

Таблица 4

	Хo	X1	X2	X3	X4	X5	X6	X7
q0					q10			q1 q3 q7
q1		q2
q2	q5
q3							q4
q4			q6
q5			q19			q8
q6			q19			q8
q7			q19			q9
q8				qo				q19
q9				qo				q19
q10		q17	q14			q11
q11					q12
q12	q13
q13						q19
q14					q15
q15	q16
q16						q19
q17					q18
q18						q19
q19

Рис.1

Анализируя полученный граф переходов, можно убедиться, что автомат допускает те и только те цепочки входных символов, которые принадлежат языку L(G"), порождаемому грамматикой G".