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