Контекстно-свободные языки

Вспомним КС-грамматику $G_{4}$, приведённую в примере 2.4. Для удобства переименуем её переменные в одиночные буквы следующим образом.

Приведите деревья вывода и выводы для каждой строки.

Ответьте на каждый пункт для следующей контекстно-свободной грамматики $G$.

Приведите контекстно-свободные грамматики, порождающие следующие языки. Во всех пунктах алфавит $\Sigma$ равен 0,1.

Приведите неформальные описания и диаграммы состояний автоматов с магазинной памятью для языков из упражнения 2.4. Во всех пунктах алфавит $\Sigma$ равен 0,1.

Приведите контекстно-свободные грамматики, порождающие следующие языки.

Приведите неформальные словесные описания автоматов с магазинной памятью для языков из упражнения 2.6.

Покажите, что строка the girl touches the boy with the flower имеет два различных левосторонних вывода в грамматике $G_{2}$ со стр. 103. Опишите словесно два различных смысла этого предложения.

Приведите контекстно-свободную грамматику, порождающую язык

Является ли ваша грамматика неоднозначной? Почему да или почему нет?

Приведите неформальное описание автомата с магазинной памятью, распознающего язык $A$ из упражнения 2.9.

Преобразуйте КС-грамматику $G_{4}$ из упражнения 2.1 в эквивалентный МП-автомат, используя процедуру из теоремы 2.20.

Преобразуйте КС-грамматику $G$ из упражнения 2.3 в эквивалентный МП-автомат, используя процедуру из теоремы 2.20.

Пусть $G=(V, \Sigma , R, S)$ — следующая грамматика. $V=\left\{ S, T, U\right\}$; $\Sigma =\left\{ 0, \# \right\}$; а $R$ — следующее множество правил:

Преобразуйте следующую КС-грамматику в эквивалентную КС-грамматику в нормальной форме Хомского, используя процедуру из теоремы 2.9.

Приведите контрпример, показывающий, что следующая конструкция не доказывает, что класс контекстно-свободных языков замкнут относительно операции звезды. Пусть $A$ — КС-язык, порождаемый КС-грамматикой $G=(V, \Sigma , R, S)$. Добавим новое правило $S \rightarrow S S$ и назовём получившуюся грамматику $G^{\prime }$. Предполагается, что эта грамматика порождает $A^{*}$.

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

Используя результаты упражнения 2.16, приведите ещё одно доказательство того, что каждый регулярный язык является контекстно-свободным, показав, как напрямую преобразовать регулярное выражение в эквивалентную контекстно-свободную грамматику.

• Пусть КС-грамматика $G$ — следующая грамматика.

Дайте простое словесное описание $L(G)$. Используя это описание, приведите КС-грамматику для $\overline{L(G)}$ — дополнения $L(G)$.

Пусть $A / B=\left\{ w \mid w x \in A\text{ для некоторого }x \in B\right\}$. Покажите, что если $A$ контекстно-свободен, а $B$ регулярен, то $A / B$ контекстно-свободен.

• Пусть $\Sigma =\left\{ \mathrm{a}, \mathrm{b}\right\}$. Приведите КС-грамматику, порождающую язык строк, в которых букв a вдвое больше, чем букв b. Докажите, что ваша грамматика верна.

• Пусть $C=\left\{ x \# y \mid x, y \in \left\{ 0,1\right\}^{*} \text{ и } x \neq y\right\}$. Покажите, что $C$ является контекстно-свободным языком.

• Пусть $D=\left\{ x y \mid x, y \in \left\{ 0,1\right\}^{*}, \left|x\right|=\left|y\right|, \text{ но } x \neq y\right\}$. Покажите, что $D$ является контекстно-свободным языком.

• Пусть $E=\left\{ \mathrm{a}^{i} \mathrm{~ b}^{j} \mid i \neq j \text{ и } 2 i \neq j\right\}$. Покажите, что $E$ является контекстно-свободным языком.

Для произвольного языка $A$ пусть $\operatorname {SUFFIX}(A)=\left\{ v \mid u v \in A\text{ для некоторой строки }u\right\}$. Покажите, что класс контекстно-свободных языков замкнут относительно операции SUFFIX.

Покажите, что если $G$ — КС-грамматика в нормальной форме Хомского, то для любой строки $w \in L(G)$ длины $n \geq 1$ любой вывод $w$ требует ровно $2 n-1$ шагов.

• Пусть $G=(V, \Sigma , R,\langle$ STMT $\rangle )$ — следующая грамматика.

$G$ — грамматика, естественно выглядящая как фрагмент языка программирования, но $G$ неоднозначна.

• Приведите однозначные КС-грамматики для следующих языков.

• Покажите, что язык $A$ из упражнения 2.9 существенно неоднозначен.

Используя лемму о накачке, покажите, что следующие языки не являются контекстно-свободными.

Пусть $B$ — язык всех палиндромов над $\left\{ 0,1\right\}$, содержащих поровну нулей и единиц. Покажите, что $B$ не является контекстно-свободным.

Пусть $\Sigma =\left\{ 1,2,3,4\right\}$ и $C=\left\{ w \in \Sigma^{*} \mid \text{в } w \text{ число единиц равно числу двоек, а число троек равно числу четвёрок}\right\}$. Покажите, что $C$ не является контекстно-свободным.

• Покажите, что $F=\left\{ \mathrm{a}^{i} \mathrm{~ b}^{j} \mid i=k j \text{ для некоторого положительного целого } k\right\}$ не является контекстно-свободным.

Рассмотрим язык $B=L(G)$, где $G$ — грамматика из упражнения 2.13. Лемма о накачке для контекстно-свободных языков, теорема 2.34, утверждает существование длины накачки $p$ для $B$. Каково минимальное значение $p$, для которого работает лемма о накачке? Обоснуйте свой ответ.

Пусть $G$ — КС-грамматика в нормальной форме Хомского, содержащая $b$ переменных. Покажите, что если $G$ порождает некоторую строку, для которой существует вывод не менее чем из $2^{b}$ шагов, то $L(G)$ бесконечен.

Приведите пример языка, который не является контекстно-свободным, но ведёт себя как КС-язык в лемме о накачке. Докажите, что ваш пример работает. (См. аналогичный пример для регулярных языков в задаче 1.54.)

• Докажите следующую усиленную форму леммы о накачке, в которой обе части $v$ и $y$ должны быть непустыми при разбиении строки $s$. Если $A$ — контекстно-свободный язык, то существует число $k$, такое что для любой строки $s \in A$ длины не менее $k$ строку $s$ можно разбить на пять частей, $s=u v x y z$, удовлетворяющих условиям:

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

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

Задача 1.42: Для языков $A$ и $B$ перемешиванием $A$ и $B$ называется язык

• Будем говорить, что язык префиксно замкнут, если все префиксы каждой строки языка также принадлежат этому языку. Пусть $C$ — бесконечный, префиксно замкнутый, контекстно-свободный язык. Покажите, что $C$ содержит бесконечное регулярное подмножество.

• Вспомните определения $N O P R E F I X(A)$ и $N O E X T E N D(A)$ из задачи 1.40.

• Пусть $Y=\left\{ w \mid w=t_{1} \# t_{2} \# \cdots \# t_{k} \text{ при } k \geq 0, \text{ каждое } t_{i} \in 1^{*}, \text{ и } t_{i} \neq t_{j}, \text{ как только } i \neq j\right\}$. Здесь $\Sigma =\left\{ 1, \# \right\}$. Докажите, что $Y$ не является контекстно-свободным.

Для строк $w$ и $t$ будем писать $w \stackrel{\circ }{=} t$, если символы $w$ являются перестановкой символов $t$. Иными словами, $w \stackrel{\circ }{=} t$, если $t$ и $w$ содержат одни и те же символы в одинаковых количествах, но, возможно, в другом порядке. Для произвольной строки $w$ определим $\operatorname {SCRAMBLE}(w)=\left\{ t \mid t \stackrel{\circ }{=} w\right\}$. Для произвольного языка $A$ положим $\operatorname {SCRAMBLE}(A)=\left\{ t \mid t \in \operatorname {SCRAMBLE}(w)\text{ для некоторого }w \in A\right\}$.

Если $A$ и $B$ — языки, определим $A \diamond B=\left\{ x y \mid x \in A\text{ и }y \in B\text{ и }\left|x\right|=\left|y\right|\right\}$. Покажите, что если $A$ и $B$ — регулярные языки, то $A \diamond B$ — КС-язык.

• Пусть $A=\left\{ w t w^{\mathcal{R}} \mid w, t \in \left\{ 0,1\right\}^{*} \text{ и } \left|w\right|=\left|t\right|\right\}$. Докажите, что $A$ не является КС-языком.

Рассмотрим следующую КС-грамматику $G$:

Опишите $L(G)$ и покажите, что $G$ неоднозначна. Приведите однозначную грамматику $H$, для которой $L(H)=L(G)$, и наметьте доказательство того, что $H$ однозначна.

Пусть $\Sigma =\left\{ 0,1\right\}$, и пусть $B$ — совокупность строк, содержащих хотя бы одну единицу во второй половине. Иными словами, $B=\left\{ u v \mid u \in \Sigma^{*}, v \in \Sigma^{*} 1 \Sigma^{*} \text{ и } \left|u\right| \geq \left|v\right|\right\}$.

Пусть $\Sigma =\left\{ 0,1\right\}$. Пусть $C_{1}$ — язык всех строк, содержащих единицу в своей средней трети. Пусть $C_{2}$ — язык всех строк, содержащих две единицы в своей средней трети. Так, $C_{1}=\left\{ x y z \mid x, z \in \Sigma^{*}, y \in \Sigma^{*} 1 \Sigma^{*}, \text{ где } \left|x\right|=\left|z\right| \geq \left|y\right|\right\}$, а $C_{2}=\left\{ x y z \mid x, z \in \Sigma^{*}, y \in \Sigma^{*} 1 \Sigma^{*} 1 \Sigma^{*}, \text{ где } \left|x\right|=\left|z\right| \geq \left|y\right|\right\}$.

• Мы определили вращательное замыкание языка $A$ как $R C(A)=\left\{ y x \mid x y \in A\right\}$. Покажите, что класс КС-языков замкнут относительно вращательного замыкания.

• Мы определили CUT языка $A$ как $C U T(A)=\left\{ y x z \mid x y z \in A\right\}$. Покажите, что класс КС-языков не замкнут относительно операции CUT.

Покажите, что каждая ДКС-грамматика (DCFG) является однозначной КС-грамматикой.

Покажите, что каждая ДКС-грамматика порождает беспрефиксный язык.

• Покажите, что класс ДКС-языков (DCFL) не замкнут относительно следующих операций:

Пусть $G$ — следующая грамматика:

Пусть $G_{1}$ — следующая грамматика, которую мы ввели в примере 2.45. Используя $D K$-тест, покажите, что $G_{1}$ не является ДКС-грамматикой.

• Пусть $A=L\left(G_{1}\right)$, где $G_{1}$ определена в задаче 2.55. Покажите, что $A$ не является ДКС-языком. (Подсказка: предположите, что $A$ — ДКС-язык, и рассмотрите его ДМП-автомат $P$. Измените $P$ так, чтобы его входной алфавит стал $\left\{ \mathrm{a}, \mathrm{b}, \mathrm{c}\right\}$. Когда он впервые попадает в допускающее состояние, пусть он с этого момента считает буквы c буквами b во входной строке. Какой язык будет допускать изменённый $P$?)

• Пусть $B=\left\{ \mathrm{a}^{i} \mathrm{~ b}^{j} \mathrm{c}^{k} \mid i, j, k \geq 0, \text{ и } i=j \text{ или } i=k\right\}$. Докажите, что $B$ не является ДКС-языком.

• Пусть $C=\left\{ w w^{\mathcal{R}} \mid w \in \left\{ 0,1\right\}^{*}\right\}$. Докажите, что $C$ не является ДКС-языком. (Подсказка: предположим, что когда некоторый ДМП-автомат $P$ запущен в состоянии $q$ с символом $x$ на вершине стека, $P$ никогда не опускает стек ниже $x$, независимо от того, какую входную строку $P$ читает с этого момента. В таком случае содержимое стека $P$ в этот момент не может влиять на его дальнейшее поведение, так что дальнейшее поведение $P$ может зависеть только от $q$ и $x$.)

• Если запретить $\varepsilon$-правила в КС-грамматиках, можно упростить $D K$-тест. В упрощённом тесте достаточно проверить, что у каждого допускающего состояния $D K$ есть ровно одно правило. Докажите, что КС-грамматика без $\boldsymbol {\varepsilon }$-правил проходит упрощённый $D K$-тест тогда и только тогда, когда она является ДКС-грамматикой.