Преобразование регулярной грамматики к автоматному виду

Имеется регулярная грамматика G(VT,VN,P,S), необходимо преобразовать ее в почти эквивалентную автоматную грамматику G'(VT,VN',P',S'). Как уже было сказано выше, будем рассматривать леволинейные грамматики (для праволинейных грамматик можно легко построить аналогичный алгоритм).

Алгоритм преобразования прост и заключается он в следующей последователь­ности действий:

Шаг 1. Все нетерминальные символы из множества VN грамматики G перено­сятся во множество VN' грамматики G'.

Шаг 2. Необходимо просматривать все множество правил P грамматики G.

Если встречаются правила вида A → Ba1, A,B VN,' a1 VT или вида A → a1, A VN, a1 VT, то они переносятся во множество P' правил грамматики G' без изменений.

Если встречаются правила вида A → Ba1a2...an , n > 1, A,B VN, n > i > 0: ai VT, то во множество нетерминальных символов VN' грамматики G' добавляются сим­волы A1,A2,…, An-1, а во множество правил P' грамматики G' добавляются правила:

An→An-1an

An→An-2an-1

...........

A2→A1a2

A1→Ba1

Если встречаются правила вида A → a1a2...an , n > 1, A VN, n > i > 0: ai VT, то во множество нетерминальных символов VN' грамматики G' добавляются симво­лы A1,A2,…, An-1, а во множество правил P' грамматики G' добавляются правила:

An→An-1an

An→An-2an-1

...........

A2→A1a2

A1→a1

Если встречаются правила вида A → B или вида A → λ, то они переносятся во множество правил P' грамматики G' без изменений.

Шаг З.Просматривается множество правил P' грамматики G'. В нем ищутся пра­вила вида A → B или вида A→λ.

Если находится правило вида A → B, то просматривается множество правил P' грамматики G'. Если в нем присутствуют правила вида В → С, В →Са, В → а или В → λ, то в него добавляются правила вида A → С, A → Ca, А → а и А → λ соот­ветственно, A,B,C VN', a VT' (при этом следует учитывать, что в граммати­ке не должно быть совпадающих правил, и если какое-то правило уже присутству­ет в грамматике G', то повторно его туда добавлять не следует). Правило А → В удаляется из множества правил P'.

Если находится правило вида A → λ (и символ А не является целевым симво­лом S), то просматривается множество правил P' грамматики G'. Если в нем присутствуют правила вида В → А или В → Aa, то в него добавляются правила вида В → λ и В → а соответственно, A,B VN', a VT' (при этом следует учи­тывать, что в грамматике не должно быть совпадающих правил, и если какое-то правило уже присутствует в грамматике G', то повторно его туда добавлять не следует). Правило A → λ удаляется из множества правил P'.

Шаг 4.Если на шаге 3 было найдено хотя бы одно правило вида A → B или вида A → λ во множестве правил P' грамматики G', то надо повторить шаг 3, иначе перейти к шагу 5.

Шаг 5.Целевым символом S' грамматики G' становится символ S.

Шаги 3 и 4 алгоритма, в принципе, можно не выполнять, если грамматика не содер­жит правил вида A → B (такие правила называются цепными) или вида A → λ (такие правила называются λ -правилами). Реальные регулярные грамматики обыч­но не содержат правил такого вида. Тогда алгоритм преобразования грамматики к автоматному виду существенно упрощается.