Пред.Страница  След.Страница  Раздел   Содержание

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

Грамматики типа 2 называют контектно-свободными и бесконтекстными грамматиками ( КС-грамматики или Б-грамматики).
Правила вывода таких грамматик имеют вид:
 
<A> ® a,
 
где <A> О V_a и a О (V_т И V_a)^*.
Очевидно, что эти правила получаются из правил грамматики типа 1 при условии c₁ = c₂ = $. Поскольку контекстные условия отсутствуют, то правила КС-грамматик получаются проще, чем правила грамматик типа 1. Именно такие грамматики используются для описания языков программирования. Примером КС-грамматики может служить следующая:
 
Г_{1. 5}:
V_т = {a, b}, V_a = {<I>},
R = { <I> ® a<I>a,
<I> ® b<I>b,
<I> ® aa,
<I> ® bb}.
 
Эта грамматика порождает язык, который состоит из цепочек, каждая из которых в свою очередь состоит из двух частей, цепочки b О V_т* и зеркального отображения этой цепочки b'.
L( Г₅ ) = { bb' | b ОV_т⁺},
где V_т⁺ - это множество V_т^* без пустой цепочки. С помощью правил этой грамматики может быть построена, например, следующая цепочка:
 
<I> Ю a<I>a Ю ab<I>ba Ю aba<I>aba Ю ababbaba.

Пред.Страница  След.Страница   Раздел   Содержание