Банк задач по математике

Пример 3.44

Покажите, что $\left\{ a^{n} b^{n} c^{n} \mid n \geq 0\right\}$ не является контекстно-свободным языком.

?

Пример 3.45

Покажите, что $L=\left\{ w w \mid w \in \left\{ 0,1\right\}^{*}\right\}$ не является контекстно-свободным языком.

?

Пример 3.46

Покажите, что $L=\left\{ 0^{n} 1^{m} \mid m \leq n^{2}\right\}$ не является контекстно-свободным языком.

?

Пример 3.47

Покажите, что $L=\left\{ a^{i} b^{j} c^{k} \mid k=\max \left\{ i, j\right\} \right\}$ не является контекстно-свободным языком.

?

Пример 3.49

Покажите, что $L=\left\{ w \in \left\{ a, b, c\right\}^{*} \mid \#_{a}(w)=\#_{b}(w)=\#_{c}(w)\right\}$ не является контекстно-свободным.

?

Пример 3.50

Покажите, что если множество $L$ обладает тем свойством, что каждое его подмножество контекстно-свободно, то $L$ обязательно конечно.

?

Пример 3.52

Покажите, что $L=\left\{ a^{n} b^{n} c^{i} \mid i \neq n\right\}$ не является контекстно-свободным.

?

Пример 3.53

Покажите, что $L=\left\{ b_{i_{1}} \# b_{i_{2}} \# \cdots \# b_{i_{k}} \mid k \geq 2\text{, каждое }b_{i_{j}}\text{ является двоичным представлением целого числа }i_{j}>0\text{, и }\left(i_{1}, i_{2}, \ldots , i_{k}\right)\text{ содержит целое число, встречающееся ровно дважды}\right\}$ не является контекстно-свободным.

?

Пример 3.54

Покажите, что язык $L=\left\{ a^{i} b^{j} c^{k} \mid i=j\text{ или }j=k\right\}$ является существенно неоднозначным.

?

Пример 3.56

Язык $L$ над одноэлементным алфавитом $\left\{ 0\right\}$ является контекстно-свободным тогда и только тогда, когда он регулярен.

?

Пример 3.57

Покажите, что $\left\{ 0^{n^{2}} \mid n \geq 1\right\}$ не является пересечением $k$ контекстно-свободных языков над алфавитом $\left\{ 0,1\right\}$ ни для какого $k$ .

?

Пример 3.58

Покажите, что язык $L=\left\{ a^{m} b^{n} \mid n \neq m^{2}\right\}$ не является контекстно-свободным.

?

Пример 3.59

Покажите, что $L=\left\{ a^{p} b^{q} \mid \operatorname {gcd}(p, q)=1\right\}$ не является контекстно-свободным.

?

Задача 3.6.1

Докажите следующие варианты леммы о накачке для контекстно-свободных языков:

?

(a)

Для любого контекстно-свободного языка $L$ существует константа $K>0$ , такая что любую строку $w$ из $L$ с $\left|w\right|>K$ можно разложить в вид $w=u v_{1} v_{2} x y_{2} y_{1} z$ , удовлетворяющий следующим условиям:

(1) $\left|v_{1} v_{2} x y_{2} y_{1}\right| \leq K$ ,

(2) $\left|v_{1} y_{1}\right|>0,\left|v_{2} y_{2}\right|>0$ , и

(3) для любого $n \geq 0$ , $u v_{1}^{n} v_{2}^{n} x w y_{2}^{n} y_{1}^{n} z \in L$ .

(b)

Для любого контекстно-свободного языка $L$ существует константа $K>0$ , такая что любую строку $w$ из $L$ с $\left|w\right|>K$ можно разложить в вид $w=u v x y z$ , удовлетворяющий следующим условиям:

(1) $\left|v x y\right| \leq K$ ,

(2) $\left|v\right|>0,\left|y\right|>0$ , и

(3) для любого $n \geq 0$ , $u v^{n} x y^{n} z \in L$ .

(c)

Для любого контекстно-свободного языка $L$ и любого $k>0$ существует константа $K>0$ , такая что любую строку $w$ из $L$ с $\left|w\right|>K$ можно разложить в вид $w=u v x y z$ , удовлетворяющий следующим условиям:

(1) $\left|v y\right| \geq k$ , и

(2) для любого $n \geq 0$ , $u v^{n} x y^{n} z \in L$ .

(d)

Для любого контекстно-свободного языка $L$ и любого $k>0$ существует константа $K>0$ , такая что любую строку $w$ из $L$ с $\left|w\right|>K$ можно разложить в вид $w=u v x y z$ , удовлетворяющий следующим условиям:

(1) $\left|v\right| \geq k,\left|y\right| \geq k$ , и

(2) для любого $n \geq 0$ , $u v^{n} x y^{n} z \in L$ .

(e)

Для любого контекстно-свободного языка $L$ и любого $k>0$ существует константа $K>0$ , такая что любую строку $w$ из $L$ с $\left|w\right|>K$ можно разложить в вид $w=u v x y z$ , удовлетворяющий следующим условиям:

(1) $\left|v x y\right| \leq K$ ,

(2) $\left|v\right| \geq k,\left|y\right| \geq k$ , и

(3) для любого $n \geq 0$ , $u v^{n} x y^{n} z \in L$ .

Задача 3.6.2

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

?

(a)

$\left\{ a^{i} b^{j} c^{k} \mid i<j<k\right\}$ .

(b)

$\left\{ a^{i} b^{j} c^{k} \mid i \neq j, j \neq k, k \neq i\right\}$ .

(c)

$\left\{ a^{i} b^{j} c^{k} \mid i<j\text{ или }k<j\right\}$ .

(d)

$\left\{ a^{i} b^{j} c^{k} \mid i<j\text{ и }k<j\right\}$ .

(e)

$\left\{ a^{i} b^{j} c^{k} \mid i<j \Rightarrow k<j\right\}$ .

(f)

$\left\{ a^{i} b^{j} c^{k} \mid i<j \Leftrightarrow k<j\right\}$ .

(g)

$\left\{ a^{i} b^{i} c^{j} d^{j} \mid i, j \geq 0\right\}$ .

(h)

$\left\{ a^{i} b^{j} c^{i} d^{j} \mid i, j \geq 0\right\}$ .

(i)

$\left\{ a^{i} b^{j} c^{j} d^{i} \mid i, j \geq 0\right\}$ .

Задача 3.6.3

Далее каждую двоичную строку из $A=1(0+1)^{*}+0$ будем рассматривать как двоичное представление натурального числа. Для каждого из следующих языков определите, является ли он контекстно-свободным, и обоснуйте свой ответ.

?

(a)

$\left\{ x \# y \mid x, y \in A, x=y+3\right\}$ .

(b)

$\left\{ x \# y^{R} \mid x, y \in A, x=y+3\right\}$ .

(c)

$\left\{ x \# y \mid x, y \in A, x=3 y\right\}$ . [Указание: рассмотрите строку $y=1^{K} 0^{K}$ , где $K$ — константа из леммы о накачке.]

(d)

$\left\{ x \# y^{R} \mid x, y \in A, x=3 y\right\}$ .

(e)

$\left\{ x \# y \# z \mid x, y, z \in A, x=y+z\right\}$ . [Указание: используя свойство замкнутости, сведите эту задачу к пункту (a) выше.]

(f)

$\left\{ x \# y^{R} \# z^{R} \mid x, y, z \in A, x=y+z\right\}$ .

(g)

$\left\{ x \# y \# z \mid x, y, z \in A, x=y \cdot z\right\}$ .

(h)

$\left\{ x \# y^{R} \# z^{R} \mid x, y, z \in A, x=y \cdot z\right\}$ .

Задача 3.6.4

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

?

(a)

$\left\{ x y z \mid x z=y\text{ для некоторых }x, y, z \in \left\{ 0,1\right\}^{*}\right\}$ . [Указание: рассмотрите пересечение этого языка с регулярным языком $10100^{+} 11^{+} 10100^{+} 11^{+}$ . Заметьте, что тогда $y$ обязано начинаться с 101.]

(b)

$\left\{ x y z \mid x z=y^{R}\text{ для некоторых }x, y, z \in \left\{ 0,1\right\}^{*}\right\}$ .

(c)

$\left\{ x y z \mid x z=y x\text{ для некоторых }x, y, z \in \left\{ 0,1\right\}^{*}\right\}$ .

(d)

$\left\{ x x^{R} w w^{R} \mid x, w \in \left\{ 0,1\right\}^{*}\right\}$ .

(e)

$\left\{ x w x^{R} w^{R} \mid x, w \in \left\{ 0,1\right\}^{*}\right\}$ .

(f)

$\left\{ x w w^{R} x^{R} \mid x, w \in \left\{ 0,1\right\}^{*}\right\}$ .

Задача 3.6.5

Напомним, что $\#_{a}(x)$ обозначает число вхождений буквы $a$ в строку $x$ . Для каждого из следующих языков определите, является ли он контекстно-свободным, и обоснуйте свой ответ.

?

(a)

$\left\{ x \in \left\{ a, b\right\}^{*} \mid \#_{a}(x)<\#_{b}(x)<2 \#_{a}(x)\right\}$ .

(b)

$\left\{ x \in \left\{ a, b\right\}^{*} \mid \#_{a}(x) \neq \#_{b}(x), \#_{a}(x) \neq 2 \#_{b}(x)\right\}$ .

(c)

$\left\{ x \in \left\{ a, b\right\}^{*} \mid \#_{a}(x) \leq \#_{b}(x)\text{ или }\#_{a}(x) \geq 2 \#_{b}(x)\right\}$ .

(d)

$\left\{ x \in \left\{ a, b\right\}^{*} \mid \#_{a}(x)=2^{\#_{b}(x)}\right\}$ .

(e)

$\left\{ x \in \left\{ a, b\right\}^{*} \mid \#_{a}(x) \geq 2^{\#_{b}(x)}\right\}$ .

(f)

$\left\{ x \in \left\{ a, b, c\right\}^{*} \mid \#_{a}(x) \cdot \#_{b}(x)=\#_{c}(x)\right\}$ .

Задача 3.6.6

Покажите, что язык $\left\{ a^{i} b^{j} c^{k} d^{\ell } \mid [i=j, k=\ell ]\text{ или }[i=\ell , j=k]\right\}$ является существенно неоднозначным.

?

Задача 3.6.7

(a)(b)(c)

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

?

(a)

$\left\{ a^{m} b^{n} \mid n \neq 2^{m}\right\}$ .

(b)

$\left\{ a^{m} b^{n} c^{q} \mid q \neq m n\right\}$ . [Указание: используйте подход примера 3.58. Сначала докажите, что в одном из порождающих множеств $\Gamma_{i}$ обязательно найдётся тройка $(0,0, r)$ .]

(c)

$\left\{ a^{m} b^{n} c^{q} \mid q^{2} \neq m^{3}\text{ или }q^{2} \neq n^{3}\right\}$ .

Задача 3.6.8

(a)(b)(c)(d)

Пусть $(x)_{r}$ обозначает строку, полученную из двоичной строки $x$ заменой 0 на 1 и 1 на 0. Для каждого из следующих языков определите, является ли он контекстно-свободным, и обоснуйте свой ответ.

?

(a)

$\left\{ x(x)_{r} \mid x \in \left\{ 0,1\right\}^{*}\right\}$ .

(b)

$\left\{ w \in \left\{ 0,1\right\}^{*} \mid w \neq x(x)_{r}\text{ ни для какого }x \in \left\{ 0,1\right\}^{*}\right\}$ .

(c)

$\left\{ x(x)_{r}^{R} \mid x \in \left\{ 0,1\right\}^{*}\right\}$ .

(d)

$\left\{ w \in \left\{ 0,1\right\}^{*} \mid w \neq x(x)_{r}^{R}\text{ ни для какого }x \in \left\{ 0,1\right\}^{*}\right\}$ .

Задача 3.6.9

(a)(b)(c)(d)

?

(a)

Вспомните операцию над языками $\oplus$ , определённую в упражнении 2 раздела 2.6. Покажите, что контекстно-свободные языки не замкнуты относительно операции $\oplus$ .

(b)

Покажите, что контекстно-свободные языки не замкнуты относительно операции MIN $(L)=\left\{ x \in L \mid x\text{ не имеет собственного префикса в }L\right\}$ .

(c)

Рассмотрите операцию $\operatorname {REV}(L)=\left\{ x y^{R} z \mid x y z \in L\right\}$ и язык $L=\left\{ 0^{m} 1^{n} 0^{n} 1^{m} \mid m, n \geq 0\right\}$ . Покажите, что $L$ — контекстно-свободный язык, а $\operatorname {REV}(L)$ — нет.

(d)

Найдите контекстно-свободный язык $L$ , такой что $L_{\frac{1}{2}}=\left\{ x \mid (\exists y)\left|x\right|=\left|y\right|\text{ и }x y \in L\right\}$ не является контекстно-свободным.

Задача 3.6.10

Пусть $L$ — контекстно-свободный язык. Докажите или опровергните следующие утверждения:

?

(a)

Если $L_{1}$ регулярен, то $L_{1} \backslash L$ контекстно-свободен.

(b)

$\left\{ x \mid x x^{R} \in L\right\}$ контекстно-свободен.

(c)

$\left\{ x x^{R} \mid x \in L\text{ или }x^{R} \in L\right\}$ контекстно-свободен.

(d)

$\left\{ x x^{R} \mid x \in L\text{ и }x^{R} \in L\right\}$ контекстно-свободен.

(e)

$\left\{ x x^{R} \mid x \in L\text{ или }x^{R} \notin L\right\}$ контекстно-свободен.

(f)

$\left\{ x x^{R} \mid x \in L\text{ и }x^{R} \notin L\right\}$ контекстно-свободен.

Задача 3.6.11

Покажите, что множество всех строк над алфавитом

\left\{ \left[\begin{smallmatrix} 0 \\ 0 \\ 0 \end{smallmatrix}\right],\left[\begin{smallmatrix} 1 \\ 0 \\ 0 \end{smallmatrix}\right],\left[\begin{smallmatrix} 0 \\ 1 \\ 0 \end{smallmatrix}\right],\left[\begin{smallmatrix} 0 \\ 0 \\ 1 \end{smallmatrix}\right],\left[\begin{smallmatrix} 1 \\ 1 \\ 0 \end{smallmatrix}\right],\left[\begin{smallmatrix} 1 \\ 0 \\ 1 \end{smallmatrix}\right],\left[\begin{smallmatrix} 0 \\ 1 \\ 1 \end{smallmatrix}\right],\left[\begin{smallmatrix} 1 \\ 1 \\ 1 \end{smallmatrix}\right]\right\}

представляющих корректное умножение, не является контекстно-свободным (ср. пример 2.65).

?

Задача 3.6.12

Контекстно-свободная грамматика $G$ называется линейной грамматикой, если правая часть каждого правила $G$ содержит не более одного нетерминального символа. Язык $L$ называется линейным языком, если $L=L(G)$ для некоторой линейной грамматики $G$ . Покажите, что для любого линейного языка $L$ существует константа $K>0$ , такая что любую строку $w$ из $L$ длины $\left|w\right| \geq K$ можно разложить в вид $w=u v x y z$ , удовлетворяющий следующим условиям:

(1) $v y \neq \varepsilon$ .

(2) $\left|u v y z\right| \leq K$ .

(3) $u v^{n} x y^{n} z \in L$ для всех $n \geq 0$ .

?

Задача 3.6.13

(a)(b)(c)

Покажите, что следующие языки не являются линейными.

?

(a)

$\left\{ w \in \left\{ 0,1\right\}^{*} \mid \#_{0}(w)=\#_{1}(w)\right\}$ .

(b)

$\left\{ x y \in \left\{ 0,1\right\}^{*} \mid \left|x\right|=\left|y\right|, x \neq y\right\}$ .

(c)

$\left\{ x x^{R} w w^{R} \mid x, w \in \left\{ 0,1\right\}^{*}\right\}$ .

Леммы о накачке для контекстно-свободных языков