Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Пример 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)

.

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.