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


Упражнения


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}.

 

  •  

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

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


  •  




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