Формальные языки


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

  •  

    Пред.Страница 

    След.Страница   Раздел   Содержание


  •  




    - Начало -  - Назад -  - Вперед -