Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Пример 2. Рассмотрим пример построения по синтаксической диаграмме детерминированного конечного автомата
|
|
Рассмотрим пример построения по синтаксической диаграмме детерминированного конечного автомата. Конечный автомат в Примере 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)
. 