Теория и реализация языков программирования


         

L генерируется КЗ- грамматикой Gi.


Предположим, что L генерируется КЗ- грамматикой Gi. Во-первых, предположим, что
. Поскольку
. Но тогда по определению xi
L(Gi) - противоречие. Таким образом предположим, что xi
L. Поскольку L(Gi) = L, xi
L(Gi). Но тогда по определению
- снова противоречие. Из чего можно заключить, что L не генерируется Gi. Поскольку приведенный выше аргумент справедлив для каждой КЗ- грамматики Gi в перечислении, и поскольку перечисление содержит все КЗ-грамматики, можно заключить, что L не КЗ-язык. Поэтому L - рекурсивное множество, не являющееся контекстно-зависимым.


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





Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий