Пред.Страница След.Страница Раздел Содержание
1.3.3. Грамматики типа 2
Грамматики типа 2 называют контектно-свободными и бесконтекстными грамматиками ( КС-грамматики или Б-грамматики).
Правила вывода таких грамматик имеют вид:
<A> ® a,
где
<A> Î Va и a Î (Vт È Va)*.
Очевидно, что эти правила получаются из правил грамматики типа 1 при условии c1 = c2 = $. Поскольку контекстные условия
отсутствуют, то правила КС-грамматик получаются проще, чем правила грамматик
типа 1. Именно такие грамматики используются для описания языков
программирования. Примером КС-грамматики может служить следующая:
Г1. 5:
Vт = {a, b}, Va =
{<I>},
R = { <I> ® a<I>a,
<I> ® b<I>b,
<I> ® aa,
<I> ® bb}.
Эта грамматика порождает язык, который состоит из цепочек, каждая из которых в свою очередь состоит из двух частей, цепочки b Î Vт* и зеркального отображения этой цепочки b'.
L( Г5 ) = { bb' | b ÎVт+},
где
Vт+ - это множество Vт* без пустой цепочки. С помощью
правил этой грамматики может быть построена, например, следующая цепочка:
<I> Þ a<I>a Þ ab<I>ba Þ aba<I>aba Þ ababbaba.