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



Упражнения


1) Определите, есть ли бесполезные символы в следующей грамматике, и, если они есть,постройте приведенную грамматику
 

      Г2. 4

      :     R = {<I>®

      <A> | <B>,

          <A>®

          a<B> | b<I> | b,
          <B>®

          <A><B> | <B>a,
          <B>®

          <A><I> | b }.

        2) Постройте для заданной грамматики эквивалентную ей неукорачивающую грамматику.
         

            Г2. 5:     R = {<I> ®

            <A><B><C> ,

                <A>®

                <B><B> | $ ,
                <B> ®<C><C>

                | a ,
                <C>®

                <A><A> | b}.

              3) Для заданной грамматики постройте эквивалентную грамматику без цепных правил.
               

                  Г2. 6:     R = {<I> ®

                  a<M> ,

                      <M>®<A>

                      ,
                      <A> ®

                      a<A> | <B> ,
                      <B> ®

                      b<B> | b}

                    4) По заданной грамматике постройте грамматику без леворекурсивных правил.
                     

                        Г2. 7 :    R = {<I> ®

                        a<A> ,

                            <I> ®

                            <I>c ,
                            <I> ®

                            <A>b ,
                            <A>®

                            d }.

                          5) Проверьте, являются ли цепочки aaabb и aabbaa допускаемыми автоматом М2.
                          6) Постройте последовательность конфигураций распознавателя М3 для цепочки (a+a) и левый вывод этой цепочки. Сравните содержимое магазина и промежуточные результаты вывода.
                          7) Постройте магазинные распознаватели для следующих грамматик и проверьте их работу .
                           

                              а) Г2. 8 :      R = {<I> ®

                              <A><I> | b , <A> ®

                              <I><A> | a}.
                              б) Г2. 9 :      R = {<I> ®

                              <A><I> | a , <A> ®

                              <B><A> | b , <B> ®

                              <A>a}.

                             

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

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


                           




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