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

       

Правила вывода таких грамматик имеют




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

    называют контектно-свободными и бесконтекстными грамматиками ( КС-грамматики или Б-грамматики).
    Правила вывода таких грамматик имеют вид:
     


        <A> ® a,

         


      где <A> О

      Va
      и a О (Vт И Va)*.
      Очевидно, что эти правила получаются из правил грамматики типа 1 при условии c1

      = c2 = $.
      Поскольку контекстные условия отсутствуют, то правила КС-грамматик получаются проще, чем правила грамматик типа 1. Именно такие грамматики используются для описания языков программирования. Примером КС-грамматики может служить следующая:
       


          Г1. 5:

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

              R = { <I> ®

              a<I>a,


                <I> ® b<I>b,

                <I> ® aa,

                <I> ® bb}.


               


            Эта грамматика порождает язык, который состоит из цепочек, каждая из которых в свою очередь состоит из двух частей, цепочки

            b О Vт*
            и зеркального отображения этой цепочки b'.

              L( Г5 ) = { bb' | b ОVт+},


            где Vт+ - это множество Vт*

            без пустой цепочки. С помощью правил этой грамматики может быть построена, например, следующая цепочка:
             
              <I> Ю a<I>a

              Ю ab<I>ba Ю aba<I>aba

              Ю ababbaba.


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

             


            Содержание раздела