2. Переход от праволинейной грамматики к автоматной.
Этот этап выполняется путем расширения нетерминального словаря способом, вытекающим из возможности преобразования праволинейной грамматики в автоматную G’’=(Vt’, Vn’’, S, R’’). Для рассматриваемого примера получим множество R’’ правил вывода:
S→x4 S1; S1→x0 S2; S2→x1 A; S→x4 S3; S3→x7 S4; S4→x7 B; S→x4 C; S→x5 F;
A→x4 D; A→x6; B→x4 E; B→x6; C→x4 E; C→x6; D→x0 S; D→x4;
E→x0 S; E→x4; F→x6 F1; F1→x0 F2; F2→x5 F3; F3→x2; F→x0 F4; F4→x0 F5;
F5→x5 F6; F6→x2; F→x1 F7; F7→x2 F8; F8→x2
Таким образом, нетерминальный словарь теперь имеет вид
Vn’’ = {S1, S2, S3, S4, А, В, С, D, E, F, F1, F2, F3, F4, F5, F6, F7, F8} и его
мощность | Vn | равна 19.
3. Построение недетерминированного конечного автомата.
Рассмотрим недетерминированный конечный распознающий автомат
A=(Q, х, δ, q0, qk), где Q - множество внутренних состояний; х - входной алфавит; δ - отображение δ:x*Q→P(Q); P(Q) - множество подмножеств из Q; q0, принадлежащее Q - начальное состояние; qk, принадлежащее Q - заключительное состояние, qk≠q0.
Этот автомат зададим следующим образом. Поставим в соответствие символам нетерминального словаря Vn’’ состояния из Q, в том числе нетерминалу S - начальное состояние q0, и добавим заключительное состояние qk, в котором автомат оказывается, если цепочка предъявляемых ему символов принадлежит L(G’’). Таким образом, мощность | Q | множества Q равна | Q | = | Vn’’ | +1=20.
В данном примере нетерминальным символам, указанным в строках 1 и 3 таблицы 3, соответствует состояния автомата, перечисленные в строках 2 и 4.
Таблица 3
S |
S1 |
S2 |
S3 |
S4 |
A |
B |
C |
D |
E |
q0 |
q1 |
q2 |
q3 |
q4 |
q5 |
q6 |
q7 |
q8 |
q9 |
F |
F1 |
F2 |
F3 |
F4 |
F5 |
F6 |
F7 |
F8 |
- |
q10 |
q11 |
q12 |
q13 |
q14 |
q15 |
q16 |
q17 |
q18 |
q19 |
Заключительное состояние обозначено через q19.
Поставив правилам вывода в соответствие переходы автомата, получим таблицу переходов недетерминированного конечного автомата (табл. 4) и граф переходов (рис. 1).
Таблица (4) переходов недетерминированного конечного автомата.
Рисунок 1
Таблица 4
q |
x0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
q0 |
|
|
|
|
q1,q3,q7 |
q10 |
|
|
q1 |
q2 |
|
|
|
|
|
|
|
q2 |
|
q5 |
|
|
|
|
|
|
q3 |
|
|
|
|
|
|
|
q4 |
q4 |
|
|
|
|
|
|
|
q6 |
q5 |
|
|
|
|
q8 |
|
q19 |
|
q6 |
|
|
|
|
q9 |
|
q19 |
|
q7 |
|
|
|
|
q9 |
|
q19 |
|
q8 |
q0 |
|
|
|
q19 |
|
|
|
q9 |
q0 |
|
|
|
q19 |
|
|
|
q10 |
q14 |
q17 |
|
|
|
|
q11 |
|
q11 |
q12 |
|
|
|
|
|
|
|
q12 |
|
|
|
|
|
q13 |
|
|
q13 |
|
|
q19 |
|
|
|
|
|
q14 |
q15 |
|
|
|
|
|
|
|
q15 |
|
|
|
|
|
q16 |
|
|
q16 |
|
|
q19 |
|
|
|
|
|
q17 |
|
|
q18 |
|
|
|
|
|
q18 |
|
|
q19 |
|
|
|
|
|
q19 |
|
|
|
|
|
|
|
|