Построение недетерминированного конечного автомата
Этот автомат зададим следующим образом. Поставим в соответствие символам нетерминального словаря V’’n состояния из Q – множества внутренних состояний, в том числе нетерминалу S – начальное состояние q0, и добавим заключительное состояние qk, в котором автомат оказывается, если цепочка предъявляемых ему символов принадлежит L(G’’). Таким образом, мощность |Q| множества Q равна |Q| = |V’’n| +1. Нетерминальным символам, указанным в строке 1 таб.3, соответствуют состояния автомата, перечисленные в строке 2.
Таблица 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 |
Правилам вывода поставим в соответствие переходы автомата. Тогда получим таб.4 – таблицу переходов недетерминированного конечного автомата, соответствующего рассматриваемому примеру. Граф переходов, построенный по таб.4 показан на рис.1.
Примечание: полученный автомат является не полностью определенным (частичным), поскольку в таб. 4 есть незаполненные клетки и, кроме того, недетерминированным, поскольку в той же таблице есть клетки, содержащие пары состояний.
Таблица 4.
|
q |
x0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
q0 |
q1, q3 |
|
|
q7 |
|
|
|
q10 |
|
q1 |
|
q2 |
|
|
|
|
|
|
|
q2 |
|
|
|
|
q5 |
|
|
|
|
q3 |
|
|
|
|
|
|
|
q4 |
|
q4 |
|
|
|
|
|
q6 |
|
|
|
q5 |
|
|
|
q19 |
|
q8 |
|
|
|
q6 |
|
|
|
q19 |
|
q9 |
|
|
|
q7 |
|
|
|
q19 |
|
q9 |
|
|
|
q8 |
q0 |
|
|
q19 |
|
|
|
|
|
q9 |
q0 |
|
|
q19 |
|
|
|
|
|
q10 |
q11 |
q17 |
|
|
|
q14 |
|
|
|
q11 |
|
|
|
|
|
q12 |
|
|
|
q12 |
|
|
q13 |
|
|
|
|
|
|
q13 |
|
|
|
q19 |
|
|
|
|
|
q14 |
|
|
|
|
|
q15 |
|
|
|
q15 |
|
|
q16 |
|
|
|
|
|
|
q16 |
|
|
|
q19 |
|
|
|
|
|
q17 |
q18 |
|
|
|
|
|
|
|
|
q18 |
|
|
|
q19 |
|
|
|
|
|
q19 |
|
|
|
|
|
|
|
|
Граф переходов, построенный по табл. 4 показан на рис.1.
Рис.
1: Граф переходов исходного
(недетерминированного) автомата.