Леволинейные и праволинейные грамматики. Автоматные грамматики

К регулярным относятся два типа грамматик: леволинейные и праволинейные.

Леволинейные грамматики G(VT,VN,P,S), V = VNVT могут иметь правила двух видов: АВγ или Аγ, где A,BVN, γVT*.

В свою очередь, праволинейные грамматики G(VT,VN,P,S), V= VNVT могут иметь правила также двух видов: АγВ или Аγ, где А,ВVN, γVT*.

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

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

Среди всех регулярных грамматик можно выделить отдельный класс – автомат­ные грамматики. Они также могут быть леволинейными и праволинейными.

Леволинейные автоматные грамматики G(VT,VN,P,S), V = VNVT могут иметь правила двух видов: ABt или At, где A,BVN, tVT.

Праволинейные автоматные грамматики G(VT,VN,P,S), V = VNVT могут иметь правила двух видов: AtB или At, где A,BVN, tVT.

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

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

Чтобы классы автоматных и регулярных грамматик были полностью эквивалент­ны, в автоматных грамматиках разрешается дополнительное правило вида S, где S – целевой символ грамматики. При этом символ S не должен встречаться в правых частях других правил грамматики. Тогда язык, заданный автоматной грамматикой G, может включать в себя пустую цепочку: L(G). В таком случае автоматные леволинейные и праволинейные грамматики, так же как обычные леволинейные и праволинейные грамматики, задают регулярные языки. Поскольку реально используемые языки, как правило, не содержат пустую цепочку симво­лов, разница на пустую цепочку между этими двумя типами грамматик значения не имеет и правила вида S далее рассматриваться не будут.

Существует алгоритм, который позволяет преобразовать произвольную регуляр­ную грамматику к автоматному виду – то есть построить эквивалентную ей ав­томатную грамматику. Этот алгоритм рассмотрен ниже. Он является исклю­чительно полезным, поскольку позволяет существенно облегчить построение распознавателей для регулярных грамматик.

2.1.2. Алгоритм преобразования регулярной грамматики
к автоматному виду

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

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

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

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

Если встречаются правила вида ABa1, А,ВVN, а1VT или вида Aa1, AVN, a1VT, то они переносятся во множество Р’ правил грамматики G’ без измене­ний.

Если встречаются правила вида АВа1а2…аn, n>1, A,BVN, n>i>0: aiVT, то во множество нетерминальных символов VN’ грамматики G’ добавляются символы A1, A2, ..., An-1, а во множество правил Р’ грамматики G’ добавляются правила:

ААn-1аn

Аn-1Аn-2аn-1

…

А2А1а2

А1Bа1

Если встречаются правила вида Аа1а2…аn, n > 1, AVN, n > i > 0: aiVT, то во множество нетерминальных символов VN’ грамматики G’ добавляются символы A1, A2, ..., An-1, а во множество правил Р’ грамматики G’ добавляются правила:

ААn-1аn

Аn-1Аn-2аn-1

…

А2А1а2

А1а1

Если встречаются правила вида АВ или вида А, то они переносятся во мно­жество правил Р’ грамматики G’ без изменений.

Шаг 3. Просматривается множество правил Р’ грамматики G’. В нем ищутся пра­вила вида АВ или вида А.

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

Если находится правило вида А, то просматривается множество правил Р’ грамматики G’. Если в нем присутствует правило вида ВА или ВАа, то в него добавляются правила вида В и Ва соответственно, A,BVN’, aVT’ (при этом следует учитывать, что в грамматике не должно быть совпадающих правил, и если какое-то правило уже присутствует в грамматике G’, то повторно его туда добавлять не следует). Правило А удаляется из множества правил Р’.

Шаг 4. Если на шаге 3 было найдено хотя бы одно правило вида АВ или А во множестве правил Р’ грамматики G’, то надо повторить шаг 3, иначе перейти к шагу 5.

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

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

Конечные автоматы