6.5

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

[8/25%]
Показать
LaTeX
Пример 6.33

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

L={a2n∣n≥0} L=\left\{ a^{2^{n}} \mid n \geq 0\right\}
?
Пример 6.34

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

L={an2∣n≥1} L=\left\{ a^{n^{2}} \mid n \geq 1\right\}
?
Задача 6.5.1

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

?
Задача 6.5.2

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

?
Задача 6.5.3

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

?
Задача 6.5.4

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

?
Задача 6.5.5

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

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

?
Задача 6.5.6

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

?