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

Пример 1. Рассмотрим алгоритм построения по недетерминированному конечному автомату

Читайте также:
  1. CИТУАЦИОННЫЕ ЗАДАЧИ С ПРИМЕРАМИ РЕШЕНИЯ
  2. CИТУАЦИОННЫЕ ЗАДАЧИ С ПРИМЕРАМИ РЕШЕНИЯ
  3. CИТУАЦИОННЫЕ ЗАДАЧИ С ПРИМЕРАМИ РЕШЕНИЯ
  4. CИТУАЦИОННЫЕ ЗАДАЧИ С ПРИМЕРАМИ РЕШЕНИЯ
  5. VI. ПРИМЕРНАЯ МЕТОДИКА ОБУЧЕНИЯ УПРАЖНЕНИЯМ КУРСА СТРЕЛЬБ
  6. Августа 1792 г. Законодательное собрание во Франции отрешило короля Людовика XVI от власти и заключило его в тюрьму. Это пример проявления санкций
  7. Автомобили - идеальный пример эмпирического продукта

Рассмотрим алгоритм построения по недетерминированному конечному автомату эквивалентного ему детерминированного автомата на Примере 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.2.Трансляторы | Лексический, синтаксический и семантический анализаторы | Генератор кода. Распределение памяти. Виды переменных | Тема 2.3 Формальные языки и грамматики | Вывод цепочек |
<== предыдущая страница | следующая страница ==>
Магазинный автомат| Пример 2

mybiblioteka.su - 2015-2021 год. (0.006 сек.)