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

Пример 2.58

$\left\{ 0^{p} \mid p\text{ — простое число}\right\}$ не является регулярным языком.

?

Пример 2.60

$\left\{ 0^{n} 1^{n} \mid n \geq 0\right\}$ не является регулярным языком.

?

Пример 2.61

Покажите, что $L=\left\{ \beta \beta^{R} \mid \beta \in \left\{ 0,1\right\}^{+}\right\}$ не является регулярным языком.

?

Пример 2.62

Покажите, что $L=\left\{ \beta \beta^{R} \gamma \mid \beta \in \left\{ 0,1\right\}^{+}, \gamma \in \left\{ 0,1\right\}^{*}\right\}$ не является регулярным.

?

Пример 2.63

Покажите, что язык $L=\left\{ 0^{n} 10^{m} 10^{p} 10^{q} \mid n, m, p \geq 1, q \equiv n m(\bmod p)\right\}$ не является регулярным.

?

Пример 2.64

Рассмотрим следующую таблицу умножения на $\left\{ a, b, c\right\}$ :

$\times$	$a$	$b$	$c$
$a$	$a$	$a$	$c$
$b$	$c$	$a$	$b$
$c$	$b$	$c$	$a$

Напомним, из примера 2.28, что для любой строки $x$ из $\left\{ a, b, c\right\}^{+}$ , $\operatorname {value}(x)$ обозначает значение, получаемое перемножением символов $x$ слева направо. Покажите, что множество

L=\left\{ x y \; : \; x, y \in \left\{ a, b, c\right\} ^{*},\left|x\right|=\left|y\right|, \operatorname {value}(x)=\operatorname {value}(y)\right\}

не является регулярным.

?

Пример 2.65

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

\Gamma =\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\}

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

\begin{array}{r} 00111 \\ \times \quad 01011 \\ \hline 1111 \end{array}

следует, что данная строка принадлежит $L$ :

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

?

Пример 2.66

Покажите, что множество $L_{2}$ двоичных представлений целых чисел из множества $A=\left\{ 2^{n} \mid n \geq 1\right\}$ регулярно, а множество $L_{3}$ троичных представлений (представлений по основанию 3) целых чисел из $A$ не является регулярным.

?

Пример 2.67

Покажите, что $L=\left\{ w \in \left\{ 0,1\right\}^{*} \mid \#_{0}(w) \neq \#_{1}(w)\right\}$ не является регулярным.

?

Пример 2.68

Покажите, что $L=\left\{ a^{n} b^{m} c^{k} \mid n, m, k \geq 0, n \neq m\text{ или }m \neq k\text{ или }k \neq n\right\}$ не является регулярным.

?

Пример 2.69

Пусть $L$ — регулярный язык. Покажите, что

L^{\prime }=\left\{ x z \mid (\exists y)[\left|x\right|=\left|y\right|=\left|z\right| \text{ and } x y z \in L]\right\}

не обязательно регулярен.

?

Задача 2.8.1

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

?

(a)

$\left\{ 0^{n^{3}+3 n^{2}-2 n} \mid n \geq 0\right\}$ .

(b)

$\left\{ 0^{p} 1^{q} 0^{m} 1^{n} \mid p+q=m+n, p, q, m, n \geq 0\right\}$ .

(c)

$\left\{ 0^{m} 1^{n} \mid m, n \geq 0\text{ and }m \neq 2 n+1\right\}$ .

(d)

$\left\{ 0^{m} 1^{n} \mid 2 n \leq m \leq 3 n, m, n \geq 0\right\}$ .

(e)

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

(f)

$\left\{ 0^{p q} \mid p\text{ and }q\text{ are primes }\right\}$ .

Задача 2.8.2

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

?

(a)

Множество двоичных строк с равным числом 0 и 1.

(b)

Множество двоичных строк с равным числом вхождений 01 и 10.

(c)

Множество двоичных строк с равным числом вхождений 010 и 101.

(d)

$\left\{ x y \mid x, y \in \left\{ 0,1\right\}^{*},\left|x\right|=\left|y\right|, \#_{0}(x) \geq \#_{0}(y)\right\}$ .

(e)

$\left\{ x y z \mid x, y, z \in \left\{ 0,1\right\}^{*},\left|x\right|=\left|z\right|>0, \#_{0}(x) \geq \#_{0}(z)\right\}$ .

(f)

$\left\{ x \# y \# z \mid x, y, z\text{ — двоичные представления положительных целых чисел, удовлетворяющие }x+y=z\right\}$ .

Задача 2.8.3

(a)(b)

Пусть $\Gamma$ — алфавит из примера 2.65.

?

(a)

Покажите, что множество $L$ всех строк над алфавитом $\Gamma$ , представляющих корректное деление, не является регулярным. Например,

\begin{array}{r} 11111 \\ \times \quad 011001 \\ \hline 00011 \end{array}

из этого следует, что данная строка принадлежит $L$ :

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

(b)

Покажите, что множество всех строк над $\Gamma$ , представляющих корректное умножение, у которых второй множитель равен 3, является регулярным.

Задача 2.8.4

Верно ли, что для любого регулярного языка $L$ над $\left\{ 0,1\right\}$ множество $N(L)= \left\{ 0^{\#_{0}(x)} 1^{\#_{1}(x)} \mid x \in L\right\}$ также регулярно? Докажите свой ответ.

?

Задача 2.8.5

Докажите следующую усиленную форму леммы о накачке: для любого регулярного языка $L$ и любого положительного целого $k$ существует положительное целое $s$ , такое что любую строку $x$ из $L$ с $\left|x\right|>s$ можно разложить в $x=u v w$ , где $\left|v\right|>k$ и для любого $i \geq 0, u v^{i} w \in L$ .

?

Задача 2.8.6

Найдите регулярный язык $L$ , для которого

\widehat{L}=\left\{ x z \mid (\exists y)[\left|x\right|=\left|y\right|=\left|z\right| \text{ and } x y z y \in L]\right\}

не является регулярным.

?

Задача 2.8.7

Пусть $A$ и $B$ — регулярные множества над алфавитом $\Sigma$ . Какие из следующих языков, если такие есть, обязательно являются регулярными?

?

(a)

$\left\{ x \mid x \in A\text{ и }x^{R} \in B\right\}$ .

(b)

$\left\{ x \mid x \in A\text{ и }x^{R} \notin B\right\}$ .

(c)

$\left\{ x \mid x=x^{R}\text{ и }x \in A\right\}$ .

(d)

$\left\{ a_{1} b_{n} a_{2} b_{n-1} a_{3} b_{n-2} \cdots a_{n} b_{1} \mid a_{i}, b_{i} \in \Sigma \text{ для }1 \leq i \leq n, a_{1} a_{2} \cdots a_{n} \in A, b_{1} b_{2} \cdots b_{n} \in B\right\}$ .

(e)

$\left\{ a_{1} a_{n} a_{2} a_{n-1} a_{3} a_{n-2} \cdots a_{n} a_{1} \mid a_{i} \in \Sigma \text{ для }1 \leq i \leq n\text{, }a_{1} a_{2} \cdots a_{n} \in A\right\}$ .

(f)

$\left\{ a_{1} a_{2 n} a_{3} a_{2 n-2} a_{5} a_{2 n-4} \cdots a_{2 n-1} a_{2} \mid a_{i} \in \Sigma \text{ для }1 \leq i \leq 2 n\text{, }a_{1} a_{2} \cdots a_{n} \in A\right\}$ .

Задача 2.8.8

Рассмотрим язык

L=\left\{ x 0^{n} y 1^{n} z \mid x \in P, y \in Q, z \in R\right\}

где $P, Q$ и $R$ — непустые множества над алфавитом $\left\{ 0,1\right\}$ . Можете ли вы найти регулярные множества $P, Q, R$ , такие что $L$ не регулярен? Можете ли вы найти регулярные множества $P, Q, R$ , такие что $L$ регулярен? Что если $P, Q, R$ должны быть бесконечными регулярными множествами?

?

Задача 2.8.9

(a)(b)

?

(a)

Является ли язык $\left\{ 0^{3 m+4 n} \mid m, n \geq 0\right\}$ регулярным? Докажите свой ответ.

(b)

Пусть $L$ — язык над алфавитом $\left\{ 0\right\}$ . Покажите, что $L^{*}$ регулярен. [Подсказка: докажите и используйте тот факт, что если $a$ и $b$ — взаимно простые натуральные числа, то для любого целого числа $n \geq a b$ существуют неотрицательные целые числа $u$ и $v$ , такие что $n=u a+v b$ .]

Леммы о накачке