Преобразование неукорачивающих грамматик - часть 2
<I> ® $ }
Выполняя все возможные замены символа I в первом правиле грамматики, получаем четыре
правила вида:
- <I> ® a<I>b<I>, <I> ® ab<I>, <I>®
a<I>b, <I>® ab .
Поступая аналогично со вторым правилом, имеем:
- <I> ® b<I>a<I>, <I> ® ba<I>, <I>
® b<I>a, <I> ®
ba.
Учитывая, что начальный символ, образующий аннулирующее правило, входит в правые части
других правил грамматики, заменим правило <I> ®
$ правилами вида <I'>®
$ и <I'>®
<I> .
Построенная совокупность правил образует схему искомой неукорачивающей грамматики. Все
приведенные выше преобразования грамматик могут быть использованы и оказаться полезными при построении как конечных, так и магазинных автоматов.
Пред.Страница
След.Страница Раздел Содержание