Автоматные грамматики: способы построения детерминированного КА (ДКА) по заданному НКА
а) Заносим в таблицу переходов все состояния, заданные НКА; б) Строим подмножество состояний для каждого состояния; в) Если при построении подмножеств в пункте б) не появилось новое подмножество, то построение таблицы закончено; г) Если при построении подмножеств появились новые подмножества, то эти подмножества принимаем в качестве новых состояний искомого автомата, заносим их в таблицу переходов и повторяем пункт б); дано НКА: , построить ДКА . 1) Пусть ; 2) Распишем множество всевозможных состояния для какого-то состояния , оно будет выглядеть как: , каждому такому подмножеству множество состояний НКА поставим в соответствие одно состояние искомого . 3) Определим множество заключительных состояний искомого ДКА: и , то . 4) ,
Автоматные грамматики: приведение некоторых языков грамматик к автоматному виду. Язык называется конечным, если он состоит из конечного числа конечных слов. Утверждение: любой конечный язык порождается автоматной грамматикой. Пусть задан некоторый конечный язык , введем нетерминал и построим правила грамматики в следующем виде: Последовательно применяя эти правила можно вывести цепочку . Применяя описанную теорию ко всем цепочкам языка, получим автоматную грамматику, порождающую данный язык. Конечный преобразователь: определение КП представляет собой конечный автомат, к которому добавлена выходная лента, неограниченная с обоих сторон. На эту ленту происходит запись выходных символов. Пусть конечный преобразователь , где - входной алфавит, - алгоритм состояний, - алфавит заключительных состояний, - выходной алфавит, . Конфигурация КП: , где - состояния конечного преобразователя, - входная цепочка, - выходная цепочка. Работу КП можно представить в виде смены конфигураций. Переход от к есть такт работы конечного преобразователя. Для любой автоматной грамматики можно простроить конечный преобразователь, формирующий на выходе синтаксический разбор цепочек, порождаемых заданной грамматикой.
Контекстно-свободные грамматики (КС): определение, приведенная КС-грамматика, неукорачивающая КС-грамматика, КС-грамматика без цепных правил, КС-грамматика без леворекурсивных правил. Преобразования КС-грамматик.
Символ называется непроизводящим, если в заданной грамматике из него невозможно вывести терминальную цепочку. Символ называется недостижимым, если он не может появиться ни в одной выводимой цепочке. Символ называется бесполезным, если он непроизводящий и недостижимый. КС-грамматика называется приведенной, если она не содержит бесполезных символов.
Популярное: Почему стероиды повышают давление?: Основных причин три... Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (1082)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |