Читайте также:
|
Рассмотрим алгоритм построения по недетерминированному конечному автомату эквивалентного ему детерминированного автомата на Примере 1.
Конечный автомат в Примере 1 распознает цепочки языка (а+bb)(a+b)*. Это недетерминированный конечный автомат. Построим для него эквивалентный автомат без ε-переходов,заменив состояния автомата ε-замыканием.
Таблица переходов для эквивалентного детерминированного автомата.
| a | b | |
| po={qo;q1} | p2 | p1 |
| p1={q2} | p2 | |
| p2={q2;q3} | p3 | p2 |
| p3={qo;q1;q2;q3} | p3 | p2 |
(Шаг 1 + Шаг 2).
Построим автоматную грамматику для языка из Примера 1.(Шаг 3).
Po->bP1|aP2;
P2->bP2|aP3;
P3->bP2|aP3;
P1->bP2
Рассмотрим пример вывода цепочки bbab: (Шаг 4).
Po->bP1->bbP2->bbaP3->bbabP2.
Построение дерева вывода цепочки автоматного языка выполняется сверху вниз. Корень дерева помечается начальным состоянием Ро. Если в исходной грамматике построить соответствующий детерминированный конечный автомат, то символ, помечающий каждый следующий узел, совпадает с меткой состояния, в которое переходит автомат на очередном шаге.
(Шаг 5).
Дата добавления: 2015-07-07; просмотров: 93 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Магазинный автомат | | | Пример 2 |