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



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

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

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


       




      Содержание  Назад  Вперед