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

UptoLike

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

Рубрика:

117

Упражнения

I-7.1. Используете алгоритм теоремы 7.4 для того, чтобы найти

грамматику, порождающую язык, распознаваемый Tm T, заданный в упр. I-6.2.

Возможно ли построить более простую грамматику для этого языка, в

частности, cfg ?

I-7.2. Дайте формальное доказательство неразрешимости проблемы

остановки машин Тьюринга.

I-7.3. Приведите множество, которое не является рекурсивно перечисли-

мым и дополнение которого тоже нерекурсивно перечислимо.

I-7.4. Постройте универсальную машину Тьюринга с двумя непринимаю-

щими состояниями.

I-7.5. Докажите, что не существует алгоритма, определяющего, остано-

вится ли произвольная машина Тьюринга с пустой лентой.

I-7.6. Пусть G = ({A, B}, {a, b}, P, A), где

P = { A → Ba, Ab → ε, B → BB, B → b,

A → a, Aa → Bb, B → Ba }.

Что за язык L(G)? Найдите машину Тьюринга, распознающую L(G).

Является ли язык L(G) контекстно-свободным? Регулярным?