Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 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. Тогда каждому выводу в грамматике:
S⇒A
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
.
Важной особенностью автоматных грамматик является возможность представления их с
помощью конечных графов. По графу грамматики легко отыскивается вывод нужной
цепочки. 
    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. Тогда каждому выводу в грамматике:
       S⇒A1ak⇒A2ak-1ak⇒ ... ⇒Ak-1a2a3...ak ⇒ a1a2 . . . ak однозначно соответствует
следующая последовательность команд построенного автомата A:

   Na1 → Ak-1; . . .; A2ak-1 → A1; A1ak → S.

    Таким образом, язык L(G) = L(A).
    Теорема. Для произвольного конечного автомата существует эквивалентная
леворекурсивная грамматика.
    Доказательство. Каждому состоянию произвольного автомата поставим в соответствие
нетерминальный символ грамматики, добавим нетерминал S и сделаем его аксиомой.
    Каждой команде Aa → B в множество правил включим соответствующее правило B →
Aa, причем в том случае, если B - заключительное состояние, дополнительно введем правило
S → Aa, а если A - начальное состояние, то дополнительно введем правило B → a.
    Тогда последовательности команд:

    A0a1 → A1; A1a2 → A2; . . . ; Ak-1ak → F

      соответствует следующий вывод:

   S ⇒ Ak-1ak ⇒ ... ⇒ A1a2a3...ak ⇒ a1a2a3...ak.

    Важной особенностью автоматных грамматик является возможность представления их с
помощью конечных графов. По графу грамматики легко отыскивается вывод нужной
цепочки.

Страницы