Преобразование неукорачивающих грамматик - часть 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> .
Построенная совокупность правил образует схему искомой неукорачивающей грамматики. Все
приведенные выше преобразования грамматик могут быть использованы и оказаться полезными при построении как конечных, так и магазинных автоматов.