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

Неоднозначные и эквивалентные грамматики


    Существуют грамматики, в которых одна и та же цепочка может быть получена с помощью различных выводов. Например, в грамматике Г1. 10 цепочка abc

    может быть получена с помощью двух различных выводов, и ей соответствуют два различных синтаксических дерева.

        Г1. 10:

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

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

              <A> ® a,


              <A> ® ac,


              <B> ® b,


              <B> ® cb}.

            Первый вывод этой цепочки имеет вид :
             

                1) <I> Ю <A><B>

                Ю <A>b Ю acb,



              а второй можно получить так :
               

                  2) <I> Ю <A><B>

                  Ю <A>cb Ю acb.

                Этим выводам соответствуют разные синтаксические деревья и разборы :


                 
                 

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

                    Г1. 11:

                      Vт = {0, +}, Va = {<I>},

                        R = { <I> ® 0,

                          <I> ® <I>

                          + 0,


                          <I> ® 0 +<I>

                          }.

                        Два вывода этой грамматики, порождающие одинаковые цепочки, имеют вид:

                            1) <I> Ю <I>

                            + 0 Ю <I> + 0 + 0 Ю 0 + 0 + 0,

                            2) <I> Ю 0 + <I> Ю 0 + 0 +<I> Ю 0 + 0 + 0,

                          а синтаксические деревья, соответствующие этим выводам, можно изобразить так:


                           
                           

                          Рассмотренное свойство грамматик называется неоднозначностью. Оно может быть определено следующим образом.

                         

                        Определение.   Цепочка языка L(Г) называется неоднозначной, если для её вывода существует более чем одно синтаксическое дерево. Если грамматика Г порождает неоднозначную цепочку, то она называется неоднозначной.

                         

                          Неоднозначность может существовать не только в искусственных языках. Хорошо известно, что в естественных языках могут быть предложения, допускающие неоднозначное написание. Например, "Пальто испачкало окно". В этой фразе не ясно, что является подлежащим, а что дополнением. Другим примером служит английская фраза: "They are flying planes", которая может быть понята двояко: "Они пилотируют самолет" или : Это летящие самолеты".


                          Свойство неоднозначности является крайне нежелательным для искусственных языков, поскольку оно не позволяет однозначным образом восстановить дерево вывода по заданной цепочке языка.
                          В общем случае можно сделать следующий вывод:
                          1) каждой цепочке, выводимой в грамматике, может соответствовать одно или несколько синтаксических деревьев,
                          2) каждому синтаксическому дереву могут соответствовать несколько выводов,
                          3) каждому синтаксическому дереву соответствует единственный правый и единственный левый выводы.
                          Кроме того, следует подчеркнуть, что один и тот же язык может быть получен с помощью различных грамматик.


                         
                        Определение.   Две грамматики Г1 и

                        Г2
                        называются эквивалентными, ecли они порождают один и тот же язык, т.е. 


                            L(Г1) = L(Г2).


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

                         
                         
                         


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