Пример построения грамматик

1. Вначале построим несколько цепочек заданного языка, которые могут быть представлены в следующем виде:

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

начало цепочки (символ * ),

конец цепочки (символы ** ),

непустая группа палочек,

последовательность групп палочек, разделенных звездочками.

3. Обозначим группу палочек символом <A>, а последовательность групп палочек символом .
4. Выделенные структуры можно рассматривать как списки. Так последовательность палочек представляет собой список без разделителей, элементом которого является палочка. Правила грамматики, задающей такой список, имеют вид:

<A> ® | ,

 ® | ,

 ® $.

Последовательность групп палочек, разделенных звездочкой, представляет собой список с разделителем, элементом такого списка является группа палочек

<A>, а разделителем - звездочка. Правила грамматики, задающей такой список, можно записать так:

<C> ® <A><E>,

<E> ® *<A><E>,

<E> ® $.

Учитывая, что каждая цепочка языка должна иметь начало и конец, и , выбирая в качестве начального символа грамматики , получаем правило, определяющее общий вид цепочки:

 ® *<C>**.

5. Объединяя построенные правила, окончательно получаем схему искомой грамматики в виде:

Г1. 19: R = { ® *<C>**,

<C> ® <A><E>,

<E> ® *<A><E>,