Правила вывода таких грамматик имеют
- Грамматики типа 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.
Пред.Страница След.Страница Раздел Содержание