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



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


Процедуру построения автомата рассмотрим на примере грамматики:
 

      Г1. 9:        R={<E>  ®<E> + <T> | <T>,

        <T>  ® <T>

        * <F> | <F>,


        <F>  ®

        ( <E> ) | a}.

        Для искомого автомата имеем:

        M3:  P = {a, + , * , ) , ( },   H = {E , T , F , a , + , x , ) , h0 , ( },   S = {s0 },   F = {s0}

        Для всех правил грамматики строим команды типа (1):
         

            (1)    f0

            (s0 , e , E) = {(s0 , T+E) ; (s0 , T)},


            (2)    f0

            (s0 , e , T) = {(s0 , F*T) ; (s0 , F)},


            (3)    f0

            (s0 , e , F) = {(s0 , )E( ) ; (s0 , a)},

          Для всех терминальных символов строим команды типа (2):
           

              (4)   f ( s0, a, a ) = ( s0, $ ),


              (5)   f ( s0 , + , + ) = (s0 , $ ),


              (6)   f ( s0 , * , * ) = (s0 , $ ),


              (7)   f ( s0 , ( , ( ) = (s0 , $ ),


              (8)   f ( s0 , ) , ) ) = (s0 , $ ),

            Для перехода в конечное состояние построим команду:
             

                (9)   f (s0 , e

                , h0) = ( s0 , $ ).

              Построенный автомат является недетерминированным.
              Начальную конфигурацию с цепочкой a + a*a запишем так: (s0 , a+a*a , h0E).
              Последовательность тактов работы построенного автомата, показывающая, что заданная  цепочка  допустима, имеет вид:
               

                  (s0 , a+a*a , h0E)   |--   (s0 , a+a*a , h0T+E)   |--
                  (s0 , a+a*a , h0T+T)   |--   (s0 , a+a*a , h0T+F)   |--
                  (s0 , a+a*a , h0T+a)   |--   (s0 , +a*a , h0T+)   |--
                  (s0 , a*a , h0T)    |--    (s0 , a*a , h0F*T)    |--
                   (s0 , a*a , h0F*F)    |--    (s0 , a*a , h0F*a)    |--
                  (s0 , *a , h0F* )    |--    (s0 , a , h0F)    |--
                  (s0 , a , h0a)    |--    (s0 , $ , h0)    |--



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