Построение КА по регулярной грамматике

 

Вход: Регулярная грамматика .

Выход: КА .

Шаг 1. Пополнить грамматику правилом , где и - новый нетерминал, для каждого правила вида , если в грамматике нет соответствующего ему правила , где .

Шаг 2. Начальный символ грамматики принять за начальное состояние КА . Из нетерминалов образовать множество состояний автомата , а из терминалов – множество символов входного алфавита .

Шаг 3. Каждое правило преобразовать в функцию переходов , где .

Шаг 4. Во множество заключительных состояний включить все вершины, помеченные символами из правил вида , для которых имеются соответствующие правила , где .

Шаг 5. Если в грамматике имеется правило , где - начальный символ грамматики, то поместить во множество заключительных состояний.

Шаг 6. Если получен НКА, то преобразовать его в ДКА.

 

ПримерДана регулярная грамматика с правилами . Построить по регулярной грамматике конечный автомат.

Решение задачи состоит из следующей последовательности действий.

1 Построим по регулярной грамматике КА.

1.1 Пополним грамматику правилами и , где - новый нетерминал.

1.2 Начальное состояние конечного автомата . Множество состояний автомата , множество символов входного алфавита .

1.3 Значения сформированной функции переходов даны в таблице 2.7.

 

Таблица 2.7 – Функция переходов автомата

 

S A B N
a A, B A N
b N B

 

1.4 Множество заключительных состояний .

1.5 Для начального символа грамматики e-правила отсутствуют.

Конечный автомат М - недетерминированный, граф НКА представлен на рисунке 2.5.

 

 
 

 


Рисунок 2.5 - Граф НКА

 

 








Дата добавления: 2016-03-27; просмотров: 1766;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.004 сек.