1.3. Типы формальных языков и грамматик

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

1.3.1. Грамматики типа 0

Грамматики типа 0, которые называютграмматиками общего вида, не имеют никаких ограничений на правила порождения. Любое правило

r = 

может быть построено с использованием произвольных цепочек    (V_т V_a)*. Например,

<T><W> <W><T>  или  x<A>b<C><D> x<H><D>.

1.3.2. Грамматики типа 1

Грамматики типа 1, которые называют такжеконтекстно-зависимыми грамматиками,не допускают использования любых правил. Правила вывода в таких грамматиках должны иметь вид:

₁<A>₂ ₁₂,

где ₁,₂- цепочки, возможно пустые, из множества (V_т  V_a)*,символ<А> V_a и цепочкаw (V_т  V_a)*. Цепочки₁ и₂остаются неизменными при применении правила, поэтому их называют контекстом (соответственно левым и правым), а грамматику - контекстно зависимой.

Грамматики типа 1 значительно удобнее на практике, чем грамматики типа 0, поскольку в левой части правила заменяется всегда один нетерминальный символ, который можно связать с некоторым синтаксическим понятием, в то время как в грамматике типа 0 можно заменять сразу несколько символов, в том числе и терминальных.

Например, грамматика:

Г_{1. 4}:

V_т = {a, b, c, d}, V_a = {<I>, <A>, <B>}

R = { <I> aA<I>,

A<I> AA<I>, AAA A<B>A, A b, b<B>A bcdA, b<I> ba }

 

является контекстно-зависимой, поскольку второе и шестое правила имеют непустой левый контекст, а третье и пятое правила содержат оба контекста. Вывод в такой грамматике может иметь вид:  

<I> a<A><I> a<A><A><I> ab<A><I> abb<I> abba.

1.3.3. Грамматики типа 2

Грамматики типа 2называютконтектно-свободнымиибесконтекстными грамматиками (КС-грамматики или Б-грамматики). Правила вывода таких грамматик имеют вид:

<A>,

где <A> V_aи(V_т  V_a)^*. Очевидно, что эти правила получаются из правил грамматики типа 1 при условии ₁ = ₂ = $.Поскольку контекстные условия отсутствуют, то правила КС-грамматик получаются проще, чем правила грамматик типа 1. Именно такие грамматики используются для описания языков программирования. Примером КС-грамматики может служить следующая:

Г_{1. 5}:

V_т = {a, b}, V_a = {<I>},

R = { <I> a<I>a,

<I>b<I>b, <I>aa, <I>bb}.

 

Эта грамматика порождает язык, который состоит из цепочек, каждая из которых в свою очередь состоит из двух частей, цепочки V_т*и зеркального отображения этой цепочки'.

L( Г₅ ) = { ' | V_т⁺},

где V_т⁺- это множествоV_т^*без пустой цепочки. С помощью правил этой грамматики может быть построена, например, следующая цепочка:

<I>a<I>aab<I>baaba<I>abaababbaba.

1.3.4. Грамматики типа 3

Грамматики типа 3называютавтоматными грамматиками (А - грамматиками). Правила вывода в таких грамматиках имеют вид:

<A>a или<A>a<B>или<A><B> a,

где a V_т, <A>, <B>V_a,причем грамматика может иметь только правила вида<A> a<B>- правосторонние правила, либо только  вида<A><B>a- левосторонние правила. Примерами автоматных грамматик могут служить правосторонняя грамматика Г_{1. 6}и левосторонняя грамматикаГ_{1. 7}.

Г_{1. 6}:

V_т = {a, b}, V_a = {<I>, <A>},

R = { <I> a<I>,

<I>a<A>, <A>b<A>, <A>b<Z>, <Z> $ }.

Г_{1. 7}:

V_т = {a, b}, V_a = {<I>, <A>},

R = { <I><A>b,

<A><A>b, <A><Z>a, <Z><Z>a, <Z> $ }.

 

Эти грамматики являются эквивалентными и порождают язык

L(Г₇) = {a...ab...b | n,m > 0}.

Между множествами языков различных типов существует отношение включения:

{ L _{типа 3} }  { L _{типа 2} }{ L _{типа 1} }{ L _{типа 0}}.

Доказано, что существуют языки типа 0, не являющиеся языками типа 1, языки типа 2, не являющиеся языками типа 1, и языки типа 3, не являющиея языками типа 2.

Учитывая, что наибольшее практическое применение находят грамматики типа 2 и типа 3, дальнейшее изложение посвящается рассмотрению именно этих типов грамматик.