Контекстно-зависимые языки

Найдите контекстно-зависимую грамматику для языка

Найдите контекстно-зависимую грамматику для языка

Постройте контекстно-зависимые грамматики для языков из примеров 4.17 и 4.18, а также для языков из упражнений 3(b)-3(i) раздела 4.5.

Завершите последнюю часть доказательства теоремы 6.35. То есть опишите, как присоединить самый левый и самый правый пробелы к соседним символам, чтобы преобразовать грамматику $G_{2}$ в контекстно-зависимую грамматику.

Покажите, что класс контекстно-зависимых языков замкнут относительно объединения, пересечения, конкатенации и замыкания Клини.

Найдите рекурсивный язык $L$, не являющийся контекстно-зависимым.

Что не так, если для вычисления $N_{k}$ в доказательстве теоремы 6.36 использовать следующий более простой алгоритм?

Для каждого $k$, чтобы вычислить $N_{k}$, мы порождаем каждую конфигурацию $\alpha \in C_{x}$ одну за другой и для каждой недетерминированно проверяем, выполнено ли $\operatorname {reach}(\beta , \alpha , k)$ (машиной $M_{1}$), и увеличиваем счётчик для $N_{k}$ на единицу, если $\operatorname {reach}(\beta , \alpha , k)$ выполнено.

($C_{x}$ обозначает множество конфигураций $M$ на входе $x$ длины $\leq s(n)$, $M_{1}$ — это НМТ, допускающая $\operatorname {reach}(\alpha , \beta , k)$ с памятью $O(s(n)+\log k)$ для $\alpha , \beta \in C_{x}$, а $N_{k}$ обозначает число конфигураций в $C_{x}$, достижимых из фиксированной конфигурации $\beta$ не более чем за $k$ ходов. Алгоритм, реально используемый в доказательстве для вычисления $N_{k+1}$ из $N_{k}$: для каждой $\alpha \in C_{x}$ угадать, в возрастающем порядке относительно фиксированного линейного порядка $\prec$ на $C_{x}$, конфигурации $\gamma_{1} \prec \cdots \prec \gamma_{N_{k}}$, достижимые из $\beta$ за $k$ ходов (каждая проверяется через $M_{1}$), затем установить $r_{\alpha }$ в ИСТИНА, если $\operatorname {reach}(\gamma_{i}, \alpha , 1)$ выполнено для некоторого $i$ — это одно прямо проверяемое условие достижимости за один ход, не требующее дальнейшего угадывания, — и увеличить $N_{k+1}$, если $r_{\alpha }=$ ИСТИНА.)

Вспомним, из упражнения 6 раздела 3.5, понятие 2-стекового PDA. Покажите, что каждый язык, допускаемый 2-стековым PDA, является контекстно-зависимым языком.