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


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


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

 

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

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

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

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


  •  
     
     




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