Примеры классификации языков и грамматик

Классификация языков идет от простого к сложному. Если мы имеем дело с регулярным языком, то можно утверждать, что он также является и контекстно-свободным, и контекстно-зависимым, и даже языком с фразовой структурой. В то же время известно, что существуют КС-языки, которые не являются регу­лярными, и существуют КЗ-языки, которые не являются ни регулярными, ни контекстно-свободными.

Далее приводятся примеры некоторых языков указанных типов. Рассмотрим в качестве первого примера ту же грамматику для целых десятич­ных чисел со знаком G({0,1,2,3,4,5,6,7,8,9,–,+},{S,T,F},P,S):

P:

S  T | +T | –T

Т  F | TF

F 0 | l | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

По структуре своих правил данная грамматика G относится к контекстно-сво­бодным грамматикам (тип 2). Конечно, ее можно отнести и к типу 0, и к типу 1, но максимально возможным является именно тип 2, поскольку к типу 3 эту грамматику отнести никак нельзя: строка
TF | TF содержит правило TTF, которое недопустимо для типа 3, и, хотя все остальные правила этому типу соот­ветствует, одного несоответствия достаточно. Для того же самого языка (целых десятичных чисел со знаком) можно построить и другую грамматику G’({0,1,2,3,4,5,6,7,8,9,–,+},{S,Т},Р,S):

P:

S  T | +T | –T

Т  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0Т | 1T | 2T | 3Т | 4T | 5T | 6T | 7T | 8T | 9T

По структуре своих правил грамматика G’ является праволинейной и может быть отнесена к регулярным грамматикам (тип 3).

Для этого же языка можно построить эквивалентную леволинейную грамматику (тип 3) G”({0,1,2,3,4,5,6,7,8,9,–,+},{S,T},P,S):

Р;

Т  + | – | 

S  Т0 | Т1 | Т2 | ТЗ | Т4 | Т5 | Тб | Т7 | Т8 | Т9 | S0 | Sl | S2 | S3 | S4 | S5 | S6 | S7 | S8 | S9

Следовательно, язык целых десятичных чисел со знаком, заданный грамматика­ми G, G’ и G”, относится к регулярным языкам (тип 3).

В качестве второго примера возьмем грамматику G2({0,1},{A,S},P,S) с правила­ми Р:

S  0А1

0А  00А1

А  

Эта грамматика относится к типу 0. Она определяет язык, множество предложе­ний которого можно было бы записать так: L(G2) = {0n1n| n > 0}.

Для этого же языка можно построить также контекстно-зависимую грамматику G2'({0,1},{A,S},P’,S) с правилами Р’:

S  0А1 | 01

0А  00А1 | 001

Однако для того же самого языка можно использовать и контекстно-свободную грамматику G2"({0,1},{S},P”,S) с правилами Р”:

S  0S1 | 01

Следовательно, язык L = {0n1n| n > 0} является контекстно-свободным (тип 2).

В третьем примере рассмотрим грамматику G3({а,b,с},{В,С,D,S},Р,S) с правила­ми Р:

S  BD

В  аВbС | аb

Сb  bС

CD  Dc

bDc  bcc

abD  abc

Эта грамматика относится к типу 1. Очевидно, что она является неукорачиваю­щей. Она определяет язык, множество предложений которого можно было бы за­писать так: L(G3)={аnbncn| n > 0}. Известно, что этот язык не является КС-язы­ком, поэтому для него нельзя построить грамматики типов 2 или 3.

Язык L = { аnbncn| n > 0} является контекстно-зависимым (тип 1).

Цепочки вывода. Сентенциальная форма

Вывод. Цепочки вывода

Выводом называется процесс порождения предложения языка на основе правил определяющей язык грамматики. Чтобы дать формальное определение процессу вывода, необходимо ввести еще несколько дополнительных понятий.

Цепочка β = 12называется непосредственно выводимой из цепочки α = 12в грамматике G(VT,VN,P,S), V = VTVN, 1,,2V*, V+, если в граммати­ке G существует правило:     Р. Непосредственная выводимость цепочки β из цепочки α обозначается так: αβ. Иными словами, цепочка β выводима из цепочки α в том случае, если можно взять несколько символов в цепочке α, заме­нить их на другие символы согласно некоторому правилу грамматики и полу­чить цепочку β.
В формальном определении непосредственной выводимости любая из цепочек 1или 2(а равно и обе эти цепочки) может быть пустой. В предельном случае вся цепочка α может быть заменена на цепочку β, тогда в грамматике G должно существовать правило: αβ  Р.

Цепочка β называется выводимой из цепочки α (обозначается α*β) в том слу­чае, если выполняется одно из двух условий:

 β непосредственно выводима из α (αβ);

  γ, такая, что: γ выводима из α и β непосредственно выводима из γ (α*γ и γβ).

Это рекурсивное определение выводимости цепочки. Суть его заключается в том, что цепочка β выводима из цепочки α, если αβ или же если можно построить последовательность непосредственно выводимых цепочек от α к β следующего вида: αγ1…γi…γnβ, n1. В этой последовательности каждая последую­щая цепочка γiнепосредственно выводима из предыдущей цепочки γi-1.

Такая последовательность непосредственно выводимых цепочек называется вы­водом или цепочкой вывода. Каждый переход от одной непосредственно выводи­мой цепочки к следующей в цепочке вывода называется шагом вывода. Очевидно, что шагов вывода в цепочке вывода всегда на один больше, чем промежуточных цепочек. Если цепочка β непосредственно выводима из цепочки α: αβ, то име­ется всего один шаг вывода.

Если цепочка вывода из α к β содержит одну или более промежуточных цепочек (два или более шагов вывода), то она имеет специальное обозначение α+β (го­ворят, что цепочка β нетривиально выводима из цепочки α). Если количество шагов вывода известно, то его можно указать непосредственно у знака выводи­мости цепочек. Например, запись α4β означает, что цепочка β выводится из це­почки α за 4 шага вывода.

Возьмем в качестве примера ту же грамматику для целых десятичных чисел со знаком G ({0,l,2,3,4,5,6,7,8,9,–,+},{S,T,F},P,S):

Р:

S  T | +T | –T

Т  F | TF

F  0|l|2|3|4|5|6|7|8|9

Построим в ней несколько произвольных цепочек вывода:

1. S  –Т  –TF  –TFF  –FFF  –4FF  –47F  –479

2. S  Т  TF  Т8  F8  18

3. Т  TF  T0  TF0  T50  F50  350

4. TFT  TFFT  TFFF  FFFF  1FFF  1FF4  10F4  1004

5. F  5

Получили следующие выводы:

1. S  * –479 или S  + –479 или S  7 –479

2. S  * 18 или S  + 18 или S  5 18

3. Т  * 350 или Т  + 350 или Т  6 350

4. TFT  * 1004 или TFT  + 1004 или TFT  7 1004

5. F  * 5 или F 15 (утверждение F  + 5 неверно!)

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