1.2.2. Примеры, иллюстрирующие первичные понятия

Рассмотрим несколько примеров, иллюстрирующих введенные понятия:

а) Задана грамматика Г_{1. 0} и требуется определить язык, порождаемый этой грамматикой:

Г_{1. 0}:      V_т = {a, b, c}, V_a = {<I>}, R = {<I>  abc}.

Схема грамматики содержит одно правило, поэтому Г_{1. 0} порождает язык из одного слова

L(Г_{1. 0}) = {abc}.

 b) Задана грамматика Г_{1. 1} и требуется определить язык, порождаемый этой грамматикой .

Г_{1. 1} :      V_т = {a, b, c}, V_a = {<I>, <B>, <C>}

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

<B> <C>d, <B> dc, <C> $}.

Построим все выводы в этой грамматике:

<I>  a<B>  a<C>d  ad, <I>  a<B>  adc.

Следовательно язык L(Г_{1. 1}) = {adc, ad}. в) Задана грамматика Г_{1. 2} и требуется определить язык, порождаемый этой грамматикой .

Г_{1. 2} :   V_a = {<I>, <A>}, V_т = {0, 1},

R = {<I>  0<A>1,

0<A>  00<A>1, <A> $}.

Рассмотрим несколько выводов с помощью правил грамматики Г_{1. 2}. Применяя первое и третье правила, получаем:

<I> 0<A>1 01.

Применяя два раза первое правило и третье, имеем

<I> 0<A>1 00<A>11 0011.

В общем случае, применяя K раз первое правило, получим в результате цепочку, содержащую K нулей и K единиц. Следовательно, язык, порождаемый грамматикой Г_{1. 2}, содержит всевозможные цепочки, в которых число нулей равно числу единиц. г) Задана грамматика Г_{1. 3} и требуется построить язык, порождаемый этой грамматикой.

Г_{1. 3} :       V_т = {a, b}, V_a = {<I>, <A>},

R = { <I> a<A>,         <A> b<A>}.

Попытка построения вывода в этой грамматике приводит нас к цепочке:

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

которая оказывается бесконечной. Другими словами, Г_{1. 3} порождает пустой язык.

1.2.3. Пустой язык

Определение.  Если язык, порождаемый грамматикой Г, не содержит ни одной конечной цепочки (конечного слова), то он называется пустым.   Утверждение.  Для того, чтобы язык L( Г ) не был пустым, в множестве R должно быть хотя бы одно правило вида r =  , где  Vт* и должен существовать вывод  <I> * .

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.