Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 40 стр.

UptoLike

Составители: 

Bc F - из состояния В при поступлении на вход терминала c автомат переходит в
заключительное состояние F;
Bc A - из состояния В при поступлении на вход терминала c автомат переходит в
состояние А;
Aa A - в состоянии А при поступлении на вход терминала а автомат остается в этом
же состоянии А;
Ab S - из состояния A при поступлении на вход терминала b автомат переходит в
состояние S.
Полученный недетерминированный конечный автомат распознает цепочки языка,
порождаемые праворекурсивной грамматикой G.
Теорема. Для произвольного конечного автомата существует эквивалентная
праволинейная грамматика.
Доказательство. Каждому состоянию произвольного автомата поставлен в соответствие
нетерминал грамматики, причем начальному состоянию будет соответствовать аксиома.
Тогда для каждой команды Ac B в множество правил грамматики включим правило A
cB, причем в случае, если B - заключительное состояние, добавим правило A c.
Эквивалентность исходного конечного автомата и построенной грамматики очевидна.
Теорема. Для каждой леворекурсивной грамматики существует эквивалентный
конечный автомат.
Доказательство. Каждому нетерминальному символу произвольной леворекурсивной
грамматики поставим в соответствие состояние конечного автомата, причем состояние,
соответствующее аксиоме S, сделаем заключительным. Добавим еще одно состояние N и
сделаем его начальным состоянием.
Каждому правилу грамматики A Ba поставим в соответствие команду автомата Вa
A. Тогда каждому выводу в грамматике:
SA
1
a
k
A
2
a
k-1
a
k
... A
k-1
a
2
a
3
...a
k
a
1
a
2
. . . a
k
однозначно соответствует
следующая последовательность команд построенного автомата A:
Na
1
A
k-1
; . . .; A
2
a
k-1
A
1
; A
1
a
k
S.
Таким образом, язык L(G) = L(A).
Теорема. Для произвольного конечного автомата существует эквивалентная
леворекурсивная грамматика.
Доказательство. Каждому состоянию произвольного автомата поставим в соответствие
нетерминальный символ грамматики, добавим нетерминал S и сделаем его аксиомой.
Каждой команде Aa B в множество правил включим соответствующее правило B
Aa, причем в том случае, если B - заключительное состояние, дополнительно введем правило
S Aa, а если A - начальное состояние, то дополнительно введем правило B a.
Тогда последовательности команд:
A
0
a
1
A
1
; A
1
a
2
A
2
; . . . ; A
k-1
a
k
F
соответствует следующий вывод:
S A
k-1
a
k
... A
1
a
2
a
3
...a
k
a
1
a
2
a
3
...a
k
.
Важной особенностью автоматных грамматик является возможность представления их с
помощью конечных графов. По графу грамматики легко отыскивается вывод нужной
цепочки.