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


Грамматики типа 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, дальнейшее изложение посвящается рассмотрению именно этих типов грамматик.

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

 




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