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



Линейно-ограниченные автоматы и их связь с контекстно-зависимыми грамматиками - часть 5


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




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