Главная страница Случайная лекция Мы поможем в написании ваших работ! Порталы: БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика Мы поможем в написании ваших работ! |
Преобразование неоднозначной А-грамматики к однозначной
Неоднозначную А-грамматику можно преобразовать к однозначной, расширив допустимые виды порождающих правил, а именно, наряду с правилами видов A → aB и A → a, разрешив правила вида A → λ, т.е. разрешив порождение пустой цепочки в правой части. Пусть задана неоднозначная А-грамматика. Вначале все правила вида A → a заменим правилами A → aF,где F – новый нетерминал, и добавим правило F → λ. Порождаемый преобразованной грамматикой язык при этом не изменится. В неоднозначной грамматике имеется по крайней мере одна группа правил вида: A → aB1 | … | aBn. (*) Обозначим B’ = {B1, …, Bn}, т.е. новый нетерминал B’ соответствует множеству B1, …, Bn нетерминалов. Вместо группы правил (*) включим в грамматику правило: A → aB’, (**) а для всех порождающих правил вида: B1 → α1, …, Bn → αn (***) добавим правила: B’ → α1 | … |αn . (****) Если в грамматике имеется (или появится после преобразования) еще одна группа правил вида (*), то с ней проделаем аналогичные преобразования, и так до тех пор, пока не останется ни одной группы правил вида (*). После каждого такого преобразования язык не изменяется, поэтому язык не изменится и после всех этих преобразований. При этом получившаяся грамматика будет однозначной. Заметим также, что после каждого такого преобразования в грамматике появляется еще один новый нетерминал и несколько новых порождающих правил. При этом все новые нетерминалы по сути являются подмножествами первоначально заданного множества нетерминалов. Т.е. если вначале было k нетерминалов, то в преобразованной грамматике их будет меньше, чем 2k. Правда, при большом числе k количество нетерминалов может оказаться чрезмерно большим. Таким способом можно преобразовать любую неоднозначную А-грамматику, сохранив порождаемый ею язык. Отсюда следует, что все автоматные языки однозначны. Заметим, что в преобразованной грамматике появится одно или несколько правил с пустой правой частью: F → λ. При построении КА по этой грамматике каждое правило грамматики вида F → λ необходимо заменить правилом F → ┴., а каждому из нетерминалов F должно соответствовать свое заключительное состояние.
Пример 3. А-грамматика задана правилами: S → 0A| 1A, A → 0A| 1A| 0 | 1. Здесь нетерминал S – начальный. Цепочки языка, порождаемого этой грамматикой, будут состоять из последовательностей нулей и единиц длиной не менее чем 2. После преобразования правил A → 0 | 1 грамматика будет следующей: S → 0A| 1A, A → 0A| 1A| 0F | 1F, F → ┴. Из-за правил A → 0A| 1A| 0F | 1F грамматика неоднозначна, поэтому обозначим: B = {A, F}. После всех изменений грамматика будет следующей: S → 0A| 1A, A → 0 B| 1B, B → 0B | 1B | ┴ , F → ┴ . В полученной грамматике правило F → ┴ бесполезно, т.к. при любом порождении, начинающемся с нетерминала S нетерминал F не может появиться в конце цепочки и это правило никогда не будет применено. Поэтому из грамматики правило F → ┴ и нетерминал F необходимо удалить. После этого можно построить табл. 3 с правилами перехода ДКА. Заметим также, что состояние B здесь будет заключительным. Табл. 3
Если на входе этого КА будет цепочка 010┴, то его состояния в процессе работы будут изменяться следующим образом: S, A, B, B, B. Так как цепочка прочитана вся и ДКА находится в заключительном состоянии, то такая входная цепочка считается распознанной, т.е. она принадлежит языку. При входной цепочке 0┴ на втором шаге из состояния A возникнет тупик: для состояния A и входного символа ┴ перехода не задано. Это значит, что такая цепочка не принадлежит языку. Конец примера.
Дата добавления: 2015-07-26; просмотров: 188; Нарушение авторских прав Мы поможем в написании ваших работ! |