Примеры классификации языков и грамматик
Классификация языков идет от простого к сложному. Если мы имеем дело с регулярным языком, то можно утверждать, что он также является и контекстно-свободным, и контекстно-зависимым, и даже языком с фразовой структурой. В то же время известно, что существуют КС-языки, которые не являются регулярными, и существуют КЗ-языки, которые не являются ни регулярными, ни контекстно-свободными.
Далее приводятся примеры некоторых языков указанных типов. Рассмотрим в качестве первого примера ту же грамматику для целых десятичных чисел со знаком 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 эту грамматику отнести никак нельзя: строка
TF | TF содержит правило TTF, которое недопустимо для типа 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).
Цепочки вывода. Сентенциальная форма
Вывод. Цепочки вывода
Выводом называется процесс порождения предложения языка на основе правил определяющей язык грамматики. Чтобы дать формальное определение процессу вывода, необходимо ввести еще несколько дополнительных понятий.
Цепочка β = 12называется непосредственно выводимой из цепочки α = 12в грамматике G(VT,VN,P,S), V = VTVN, 1,,2V*, V+, если в грамматике G существует правило: Р. Непосредственная выводимость цепочки β из цепочки α обозначается так: αβ. Иными словами, цепочка β выводима из цепочки α в том случае, если можно взять несколько символов в цепочке α, заменить их на другие символы согласно некоторому правилу грамматики и получить цепочку β.
В формальном определении непосредственной выводимости любая из цепочек 1или 2(а равно и обе эти цепочки) может быть пустой. В предельном случае вся цепочка α может быть заменена на цепочку β, тогда в грамматике G должно существовать правило: αβ Р.
Цепочка β называется выводимой из цепочки α (обозначается α*β) в том случае, если выполняется одно из двух условий:
β непосредственно выводима из α (αβ);
γ, такая, что: γ выводима из α и β непосредственно выводима из γ (α*γ и γβ).
Это рекурсивное определение выводимости цепочки. Суть его заключается в том, что цепочка β выводима из цепочки α, если αβ или же если можно построить последовательность непосредственно выводимых цепочек от α к β следующего вида: αγ1…γi…γnβ, n1. В этой последовательности каждая последующая цепочка γ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. В принципе в этой грамматике (как, практически, и в любой другой грамматике реального языка) можно построить сколь угодно много цепочек вывода.