КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Грамматики типа 2
Грамматики типа 2 называют контектно-свободными и бесконтекстными грамматиками (КС-грамматики или Б-грамматики).
Правила вывода таких грамматик имеют вид:
<A> 
α,
где <A> 
VА и α (Vт 
VА)*.
Очевидно, что эти правила получаются из правил грамматики типа 1 при условии χ1 = χ2 = $. Поскольку контекстные условия отсутствуют, то правила КС-грамматик получаются проще, чем правила грамматик типа 1. Именно такие грамматики используются для описания языков программирования.
Примером КС-грамматики может служить следующая:
Г1. 5:
Vт = {a, b}, VА = {<I>},
R = { <I> a<I>a,
<I> b<I>b,
<I> aa,
<I> bb}
Эта грамматика порождает язык, который состоит из цепочек, каждая из которых в свою очередь состоит из двух частей, цепочки β Vт* и зеркального отображения этой цепочки β'.
L( Г5 ) = { bb' | b Vт+},
где Vт+ - это множество Vт* без пустой цепочки. С помощью правил этой грамматики может быть построена, например, следующая цепочка:
<I> 
a<I>a ab<I>ba aba<I>aba ababbaba
Дата добавления: 2015-01-29; просмотров: 80; Мы поможем в написании вашей работы!; Нарушение авторских прав |