Грамматики G1 = ({0,1}, {A,S}, P1, S) и G2 = ({0,1}, {S}, P2, S), где
P1={ S ® 0A1, 0A ® 00A1, A ® e}, P2={ S ® 0S1 | e}
являются почти эквивалентными, так как
L(G1)={0n1n | n>0}, а L(G2)={0n1n | n³0}, то есть L(G2) состоит из всех цепочек языка L(G1) и пустой цепочки, которая в L(G1) не входит.
Рассмотрим классификацию грамматик, предложенную Н.Хомским, основанную на виде их правил.
Грамматика G = (VT, VN, P, S) называется грамматикой типа 0(или грамматикой без ограничений), если на правила вывода не накладывается никаких ограничений (кроме тех, которые указаны в определении грамматики).
Грамматика G = (VT, VN, P, S) называется неукорачивающей грамматикой, если для каждого правила вывода a ® b (кроме S ® e) выполняется соотношение | a | £ | b |. В том случае, когда S ® e Î P, символ S не встречается в правых частях правил вывода.
Грамматика G = (VT, VN, P, S) называется контекстно-зависимой (КЗ), если каждое правило из P имеет вид a ® b,
где a = x1Ax2; b = x1gx2; A Î VN; g Î (VT È VN)+; x1,x2 Î (VT È VN)*.
Грамматику типа 1 можно определить как неукорачивающую либо как контекстно-зависимую.
Выбор определения не влияет на множество языков, порождаемых грамматиками этого класса, поскольку доказано, что множество языков, порождаемых неукорачивающими грамматиками, совпадает с множеством языков, порождаемых КЗ-грамматиками.
Грамматика G = (VT, VN, P, S) называетсяконтекстно-свободной (КС), если каждое правило из Р имеет вид A ® b, где A Î VN, b Î (VT È VN)+.
Грамматика G = (VT, VN, P, S) называется укорачивающей контекстно-свободной (УКС), если каждое правило из Р имеет вид A ® b, где A Î VN,
b Î (VT È VN)*.
Грамматику типа 2 можно определить как контекстно-свободную либо как укорачивающую контекстно-свободную.
Возможность выбора обусловлена тем, что для каждой УКС-грамматики существует почти эквивалентная КС-грамматика.
Грамматика G = (VT, VN, P, S) называется праволинейной, если каждое правило из Р имеет вид A ® tB либо A ® t, где A Î VN, B Î VN, t Î VT.
Грамматика G = (VT, VN, P, S) называется леволинейной, если каждое правило из Р имеет вид A ® Bt либо A ® t, где A Î VN, B Î VN, t Î VT.
Грамматику типа 3 (регулярную, Р-грамматику) можно определить как праволинейную либо как леволинейную.
Выбор определения не влияет на множество языков, порождаемых грамматиками этого класса, поскольку доказано, что множество языков, порождаемых праволинейными грамматиками, совпадает с множеством языков, порождаемых леволинейными грамматиками.
Очевидно, что в примере 2.3 грамматика G2 является неукорачивающей, грамматика G3 - контекстно-свободной, грамматика G4 - праволинейной.
Соотношения между типами грамматик:
- любая регулярная грамматика является КС-грамматикой;
- любая регулярная грамматика является УКС-грамматикой;
- любая КС-грамматика является КЗ-грамматикой;
- любая КС-грамматика является неукорачивающей грамматикой;
- любая КЗ-грамматика является грамматикой типа 0;
- любая неукорачивающая грамматика является грамматикой типа 0.
Замечание: УКС-грамматика, содержащая правила вида A ® e, не является КЗ-грамматикой и не является неукорачивающей грамматикой.
Язык L(G) называется языком типа k, если его можно описать грамматикой типа k.
Соотношения между типами языков:
- каждый регулярный язык является КС-языком, но существуют КС-языки, которые не являются регулярными (например, L = {anbn | n>0});
- каждый КС-язык является КЗ-языком, но существуют КЗ-языки, которые не являются КС-языками (например, L = {anbncn | n>0});
- каждый КЗ-язык является языком типа 0.
Замечание: УКС-язык, содержащий пустую цепочку, не является КЗ-языком.
Следует отметить, что если язык задан грамматикой типа k, то это не значит, что не существует грамматики типа k’ (k’>k), описывающей тот же язык. Поэтому, когда говорят о языке типа k, обычно имеют в виду максимально возможный номер k.
КЗ-грамматика G1 = ({0,1}, {A,S}, P1, S) и
КС-грамматика G2 = ({0,1}, {S}, P2, S), где
P1={ S ® 0A1, 0A ® 00A1, A ® e}, P2={S ® 0S1 | 01},
описывают один и тот же язык L = L(G1) = L(G2) = { 0n1n | n>0}.
Язык L является КС-языком, так как существует КС-грамматика, его описывающая. Но он не является регулярным языком, потому что не существует регулярной грамматики, описывающей этот язык [3].
