Читайте также:
|
Рассмотрим пример построения по синтаксической диаграмме детерминированного конечного автомата. Конечный автомат в Примере 2 распознает цепочки языка b+(а+bb)(b+ab)*a. Синтаксическая диаграмма для данного автомата представлена на рисунке.
Построим детерминированный конечный автомат по алгоритму, описанному выше.
Эквивалентный автомат без ε-переходов.
Таблица переходов для эквивалентного автомата из Примера 2.
| a | b | |
| p1{1} | p3 | p2 |
| p2{2;6} | p3 | |
| p3{3;4;7} | p2 | p3 |
Эквивалентный детерминированный автомат. (Шаг 1 + Шаг 2). 
Построим автоматную грамматику для языка из Примера 2.(Шаг 3).
P1->bP2|aP3;
P2->bP3;
P3->bP3|aP2;
Рассмотрим пример вывода цепочки bbab:(Шаг 4).
P1->bP2->bbP3->bbaP2->bbabP3.
Построение дерева разбора для цепочки bbab, распознаваемой автоматом Приме
ра 2. (Шаг 5)
. 
Дата добавления: 2015-07-07; просмотров: 85 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Пример 1 | | | ВВЕДЕНИЕ |