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



Грамматики типа 3


    Грамматики типа 3

    называют автоматными грамматиками (А - грамматиками). Правила вывода в таких грамматиках имеют вид:
     

        <A> ® a

        или <A> ® a<B>

        или <A> ® <B>

        a,
         

      где a О Vт, <A>, <B> О Va, причем грамматика может иметь только правила вида <A>

      ® a<B> - правосторонние правила, либо только  вида <A> ® <B>a

      - левосторонние правила. Примерами автоматных грамматик могут служить правосторонняя грамматика Г1. 6

      и левосторонняя грамматика Г1. 7.

        Г1. 6:

          Vт = {a, b}, Va = {<I>, <A>},

            R = { <I> ® a<I>,

              <I> ® a<A>,


              <A> ® b<A>,


              <A> ® b<Z>,


              <Z> ® $ }.

            Г1. 7:

              Vт = {a, b}, Va = {<I>, <A>},

                R = { <I> ® <A>b,

                  <A> ® <A>b,


                  <A> ® <Z>a,


                  <Z> ® <Z>a,


                  <Z> ® $ }.

                 

              Эти грамматики являются эквивалентными и порождают язык

              L(Г7) = {a...ab...b | n,m > 0}.

            Между множествами языков различных типов существует отношение включения:

                { L типа 3 } М

                { L типа 2 }

                М{ L типа 1 } М{ L типа 0}.

              Доказано, что существуют языки типа 0, не являющиеся языками типа 1, языки типа 2, не являющиеся языками типа 1, и языки типа 3, не являющиея языками типа 2.

              Учитывая, что наибольшее практическое применение находят грамматики типа 2 и типа 3, дальнейшее изложение посвящается рассмотрению именно этих типов грамматик.

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




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