Построение детерминированного конечного автомата

Вначале изменим грамматику таким образом, чтобы в конце любой порождаемой ею цепочки был концевой символ _┴, отличающийся от всех символов алфавита языка. Рассмотрим все правила грамматики вида: A → a. Заменим это правило двумя правилами: A → aR, R → _┴ , где R – новый нетерминальный символ.

Нетрудно видеть, что после всех таких замен в грамматике останутся только правила вида A → aB и одно единственное правило R → _┴ , при этом в конце всех порождаемых цепочек появится дополнительный концевой символ _┴ .

Алфавит входных символов КА будет совпадать с алфавитом символов языка грамматики, включая концевой символ _┴, множество состояний КА будет включать все множество нетерминалов (символов грамматики), а также дополнительное заключительное состояние F. Тогда каждое правило грамматики вида A → aB, преобразуется в правило перехода КА: (a, A) → B, а правило грамматики вида R → _┴ преобразуется в правило перехода: (_┴, R) → F.

Построенный КА будет детерминированным (ДКА), если А-грамматика однозначна. В свою очередь, А-грамматика однозначна, если для любой пары (A, a) имеется не более одного правила вида A → aB. В противном случае А-грамматика будет неоднозначной, и будет построен НКА.

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

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

A → γ₁, A → γ₂, …, A → γ_n

будем записывать:

A → γ₁| γ₂| … | γ_n .

Пример 1. А-грамматика задана правилами: S → 0A| 1A, A → 0A| 1A| 2. Здесь нетерминал S – начальный. Цепочки языка, порождаемые этой грамматикой, будут состоять из непустых последовательностей нулей и единиц, в конце которых имеется цифра 2.

После изменения грамматика будет содержать правила: S → 0A| 1A, A → 0A| 1A| 2R, R → _┴. Табл. 1 содержит правила перехода ДКА.

Табл. 1

Если на входе этого КА будет цепочка 01102_┴, то его состояния в процессе работы будут изменяться следующим образом: S, A, A, A, A, R, F. Так как цепочка прочитана вся и ДКА находится в заключительном состоянии, то такая входная цепочка считается распознанной, т.е. она принадлежит языку. При входной цепочке 0110_┴ состояния будут такими: S, A, A, A, A, и возникнет тупик: для состояния A и входного символа _┴ перехода не задано. Это значит, что такая цепочка не принадлежит языку. Входная цепочка 2_┴ также приводит к тупику: на первом же шаге из состояния S при входном символе 2 переход не задан.

Конец примера.

Дата добавления: 2015-07-26; просмотров: 181; Нарушение авторских прав

Мы поможем в написании ваших работ!