Языки и трансляции. Мартыненко Б.К. - 123 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

122
грамматики определяется по самим правилам грамматики, в которых эти
нетерминалы используются.
Заметим, что не все цепочки из 0 и 1 представляют грамматики, тем более
контекстно-зависимые грамматики. Однако по заданной цепочке можно легко
судить, является ли она csg. Поскольку имеется бесконечно много csg, мы
можем их нумеровать некоторым разумным образом: G
1
, G
2
, ... .
Доказательство теоремы теперь тривиально.
Определим язык L = {x
i
| x
i
∉ L(G
i
) }. Язык L — рекурсивен. Действительно,
по любой данной цепочке x
i
легко определить i, а затем можно сгенерировать
G
i
. Согласно теореме 2.2 имеется алгоритм, который определяет, находится ли
цепочка x
i
в языке L(G
i
), поскольку G
i
— контекстно-зависимая грамматика.
Следовательно, имеем алгоритм определения для любой цепочки x, находится
ли она в языке L.
Теперь
покажем, что язык L не порождаётся никакой контекстно-зависимой
грамматикой.
Предположим противное: язык L порождаётся csg G
j
. Пусть x
j
∈L.
Поскольку L = L(G
j
), то x
j
∈L(G
j
). Но по самому определению языка x
j
∉ L(G
j
).
Получаем противоречие, которое отвергает наше предположение о том, что
существует csg G
j
, порождающая язык L. Поскольку приведенное рассуждение
справедливо для каждой csg G
j
в перечислении, и поскольку перечисление
содержит каждую csg, мы заключаем, что язык L не является контекстно-
зависимым языком. Следовательно, L — рекурсивное множество, которое не
является контекстно-зависимым.
Что и требовалось доказать.
Упражнения
I-8.1. Построить lba, распознающий язык L = {ww | w ∈ {0, 1}
*
}.
I-8.2. Пусть M lba. Докажите, что существует lba M
1
, который всегда
останавливается независимо от того, принимается ли ввод или нет.
I-8.3. Пусть C класс устройств некоторого сорта. Предположим, что:
1. существует перечисление всех устройств класса C: M
1
, M
2
, … и
2. существует алгоритм, который по данным произвольному устройству
M∈C и вводу x определяет, примет ли M ввод x.
Используйте метод теоремы 8.3, чтобы доказать, что не все рекурсивные
множества принимаются некоторым устройством M∈C.
I-8.4. Докажите, что каждый контекстно-свободный язык принимается
детерминированным lba.
I-8.5. Постройте lba, который принимает L = {a
i
| i не простое}.
Пояснение. Сделайте построенный lba недетерминированным. Легко ли напи-
сать csg, порождающую L?

Страницы