Мегаобучалка Главная | О нас | Обратная связь  


Автоматные грамматики: способы построения детерминированного КА (ДКА) по заданному НКА




Поможем в ✍️ написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

а) Заносим в таблицу переходов все состояния, заданные НКА;

б) Строим подмножество состояний для каждого состояния;

в) Если при построении подмножеств в пункте б) не появилось новое подмножество, то построение таблицы закончено;

г) Если при построении подмножеств появились новые подмножества, то эти подмножества принимаем в качестве новых состояний искомого автомата, заносим их в таблицу переходов и повторяем пункт б);

дано НКА: , построить ДКА .

1) Пусть ;

2) Распишем множество всевозможных состояния для какого-то состояния , оно будет выглядеть как: , каждому такому подмножеству множество состояний НКА поставим в соответствие одно состояние искомого .

3) Определим множество заключительных состояний искомого ДКА: и , то .

4) ,

 

Автоматные грамматики: приведение некоторых языков грамматик к автоматному виду.

Язык называется конечным, если он состоит из конечного числа конечных слов.

Утверждение: любой конечный язык порождается автоматной грамматикой. Пусть задан некоторый конечный язык , введем нетерминал и построим правила грамматики в следующем виде:

Последовательно применяя эти правила можно вывести цепочку . Применяя описанную теорию ко всем цепочкам языка, получим автоматную грамматику, порождающую данный язык.



Конечный преобразователь: определение

КП представляет собой конечный автомат, к которому добавлена выходная лента, неограниченная с обоих сторон. На эту ленту происходит запись выходных символов.

Пусть конечный преобразователь , где - входной алфавит, - алгоритм состояний, - алфавит заключительных состояний, - выходной алфавит, .

Конфигурация КП: , где - состояния конечного преобразователя, - входная цепочка, - выходная цепочка. Работу КП можно представить в виде смены конфигураций. Переход от к есть такт работы конечного преобразователя.

Для любой автоматной грамматики можно простроить конечный преобразователь, формирующий на выходе синтаксический разбор цепочек, порождаемых заданной грамматикой.

 

Контекстно-свободные грамматики (КС): определение, приведенная КС-грамматика, неукорачивающая КС-грамматика, КС-грамматика без цепных правил, КС-грамматика без леворекурсивных правил. Преобразования КС-грамматик.


Символ называется непроизводящим, если в заданной грамматике из него невозможно вывести терминальную цепочку.

Символ называется недостижимым, если он не может появиться ни в одной выводимой цепочке.

Символ называется бесполезным, если он непроизводящий и недостижимый.

КС-грамматика называется приведенной, если она не содержит бесполезных символов.




Читайте также:



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (929)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.006 сек.)
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7