2. Классификация грамматик и языков

Формальные грамматики можно классифицировать по типу существующих в них правил вывода.

Грамматика G называется неукорачивающей грамматикой, если каждое правило из R имеет вид   , где   V⁺,   V⁺ и ||  ||.

Грамматика G называется укорачивающей грамматикой, если каждое правило из R имеет вид   , где   V⁺,   V^*.

Иерархия Хомского

T0: Грамматика G называется грамматикой типа 0 или рекурсивной грамматикой, если на правила вывода не накладывается никаких ограничений (кроме тех, которые указаны в определении грамматики –   #).

T1: Грамматика G называется грамматикой типа 1 или контекстно-зависимой (КЗ) грамматикой, если каждое правило из R имеет вид   , где  = ₁A₂;  = ₁₂; A  Vn;   V⁺; ₁, ₂  V^*.

Грамматику типа 1 можно определить как контекстно-зависимую или как неукорачивающую. Классы КЗ-грамматик и неукорачивающих грамматик эквивалентны. Доказано, что множество языков, порождаемых неукорачивающими грамматиками, совпадает с множеством языков, порождаемых КЗ-грамматиками.

Т2: Грамматика G называется грамматикой типа 1 или контекстно-свободной (КС) грамматикой, если каждое правило из R имеет вид A  , где A  Vn,   V⁺ (для неукорачивающих КС-грамматик), или A  Vn,   V^* (для укорачивающих КС-грамматик).

Т3: Грамматика G называется грамматикой типа 3 или регулярной грамматикой, грамматикой с конечным числом состояний, если каждое правило из R имеет вид A  tB (A  Bt) либо A  t, где A, B  Vn, t  Vt.

Грамматика с правилами типа A  tB является праволинейной.

Грамматика с правилами типа A  Bt является леволинейной.

Множества языков, порождаемых праволинейными и леволинейными грамматиками, совпадают.

Язык L(G) является языком типа k, если его можно описать грамматикой типа k.

Примеры:

Грамматика G и язык L типа 0

Правила G:

S  aaCFD

F  AFB | AB

AB  bBA

Ab  bA

AD  D

Cb  bC

CB  C

bCD  #

L(G) = {a² b^{n2 – 1} | n  1}.

Грамматика G и язык L типа 1

Правила G:

S  aSBC | abC

CB  BC

bB  bb

bC  bc

cC  cc

L(G) = {aⁿ bⁿ cⁿ, n  1}

Грамматика G и язык L типа 2

Правила G:

S  aQb | accb

Q  cSc

L(G) = {(ac)ⁿ (cb)ⁿ, n > 0}

Грамматика G и язык L типа 3

Правила G:

S  A | B

A  a | Ba

B  b | Bb | Ab

L(G) = { |   {a,b}⁺, где нет двух рядом стоящих а}

3. Эквивалентность грамматик и языков, соотношения между грамматиками и языками

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

Грамматики G1 и G2 сильно эквивалентны, если L(G1) = L(G2)

и грамматики приписывают цепочкам одинаковые структуры составляющих.

Пример:

G1 = ({0, 1}, {A, S}, R1, S) и G2 = ({0, 1}, {S}, R2, S)

R1: S  0A1 R2: S  0S1 | 01

A  0A1

A  #

эквивалентны, т.к. обе порождают язык L(G1) = L(G2) = {0ⁿ1ⁿ | n>0}.

Грамматики G1 и G2 условно эквивалентны, если L(G1)  {#} = L(G2)  {#}.

(если языки, ими порождаемые, отличаются не более, чем на #).

Пример:

G1 = ({0, 1}, {A, S}, R1, S) и G2 = ({0, 1}, {S}, R2, S)

R1: S  0A1 R2: S  0S1 | #

A  0A1

A  #

условно эквивалентны, так как L(G1)={0ⁿ1ⁿ | n>0}, а L(G2)={0ⁿ1ⁿ | n  0}:

L(G2) состоит из всех цепочек языка L(G1) и пустой цепочки, которая в L(G1) не входит.