Пример 2.4

Пример 2.3

1) Грамматика G1 = ({0,1}, {A,S}, P, S),

где P состоит из правил Р={ S ® 0A1, 0A ® 00A1, A ® e}

Применяя последовательно правила (S ® 0A1 ® 00A11 ® 0011), получаем цепочку 0011.

Эта грамматика порождает язык L(G1) = {0ⁿ 1ⁿ |n > 0}.

2) Грамматика G2 = ({a, b, c}, {S, B, C}, P, S),

P = {S ® aSBC, S ® aBC, CB ® BC, aB ® ab, bB ® bb, bC ® bc, cC ® cc}.

Эта грамматика порождает язык L(G2) = {aⁿ bⁿ cⁿ |n > 0}.

Действительно, применяем n - 1 раз правило 1 и получаем a^n-1 S(BC)^n-1 , затем один раз правило 2 и получаем aⁿ (BC)ⁿ , затем n(n - 1)/2 раз правило 3 и получаем aⁿBⁿCⁿ. Затем используем правило 4, получаем aⁿbB^n-1Cⁿ . Затем применяем n – 1 раз правило 5 и получаем aⁿbⁿCⁿ. Затем применяем правило 6 и n - 1 раз правило 7 и получаем aⁿbⁿcⁿ. Можно показать, что язык L(G2) состоит из цепочек только такого вида.

3) Грамматика G3 = ({0, 1},{S}, {S ® 0S1, S ® 01}, S).

Легко видеть, что цепочка 000111 Î L(G), так как существует вывод

S ® 0S1 ® 00S11 ® 00111

Нетрудно показать, что грамматика порождает язык L(G3) = {0ⁿ 1ⁿ |n > 0}.

4) Грамматика

G4 = ({0, 1},{S, A}, {S ® 0S, S ® 0A, A ® 1A, A ® 1}, S)

порождает язык L(G4) = {0ⁿ 1^m |n,m > 0}, что нетрудно показать.

Цепочка b Î (VT È VN)^* называется непосредственно выводимойиз цепочки a Î (VT È VN)⁺ в грамматике G = (VT, VN, P, S) (обозначим a ® b), если a = x₁gx₂, b = x₁dx₂, где x₁, x₂, d Î (VT È VN)^*, g Î (VT È VN)⁺ и правило вывода g ® d содержится в P.

Например, цепочка 00A11 непосредственно выводима из 0A1 в грамматике G1.

Цепочка b Î (VT È VN)^* называется выводимойиз цепочки
a Î (VT È VN)⁺ в грамматике G = (VT, VN, P, S) (обозначим a Þ b), если существуют цепочки g₀, g₁, ... , g_n (n³0), такие, что a = g₀ ® g₁ ® ... ® g_n= b.

Последовательность g₀, g₁, ... , g_n называется выводом длины n.

Например, S Þ 000A111 в грамматике G1 (см. пример 2.3), так как существует вывод S ® 0A1 ® 00A11 ® 000A111. Длина вывода равна 3.

Языком, порождаемым грамматикой G = (VT, VN, P, S), называется множество L(G)={a Î VT^* | S Þ a}.

Другими словами, L(G) - это все цепочки в алфавите VT, которые выводимы из S с помощью P.

Например, L(G1) = {0ⁿ1ⁿ | n>0}.

Цепочка a Î (VT È VN)^*, для которой S Þ a, называется сентенциальной формой в грамматике G = (VT, VN, P, S).

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

Грамматики G1 и G2 называются эквивалентными, если L(G1) = L(G2).

Грамматики 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(G1) = L(G2) = {0ⁿ1ⁿ | n>0}.

Грамматики G1 и G2 называются почти эквивалентными, если

L(G1) È {e} = L(G2) È {e}.

Другими словами, грамматики почти эквивалентны, если языки, ими порождаемые, отличаются не более чем на e.