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

Пример 2.34

Пусть $M$ — некоторый $N F A$ . Постройте $N F A M^{\prime }$ , такой что $L\left(M^{\prime }\right)= L(M)^{R}$ .

?

Пример 2.35

Пусть $f$ — подстановка над $\Sigma$ . Пусть $L \subseteq \Sigma^{*}$ — регулярный язык, и для каждого $a \in \Sigma$ язык $f(a)$ регулярен. Тогда $f(L)$ также является регулярным языком.

?

Пример 2.36

Покажите, что для любого языка $L_{2}$ , если $L_{1}$ регулярен, то $L_{1} / L_{2}$ также регулярен.

?

Пример 2.37

Пусть $L$ — регулярный язык над $\Sigma$ , $k$ — положительное целое число, а $\phi$ — отображение из $\Sigma^{k}$ в $\Sigma$ . Докажите, что

L_{1}=\left\{ \phi \left(a_{1} a_{2} \cdots a_{k}\right) \cdots \phi \left(a_{(n-1) k+1} a_{(n-1) k+2} \cdots a_{n k}\right) \mid a_{1} a_{2} \cdots a_{n k} \in L\right\}

регулярен.

?

Пример 2.38

Докажите, что если $L$ регулярен, то регулярен и $\operatorname {MIN}(L)$ .

?

Пример 2.39

Покажите, что если $A$ и $B$ — регулярные языки над $\left\{ 0,1\right\}$ , то

A \vee B=\left\{ x \vee y|x \in A, y \in B,|x|=|y|\right\}

также регулярен.

?

Пример 2.40

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

\left\{ x y \mid y x \in L\right\} .

?

Пример 2.41

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

L_{\frac{1}{2}}=\left\{ x \mid (\exists y)[\left|x\right|=\left|y\right|, x y \in L]\right\} .

?

Пример 2.42

Покажите, что если $L$ — регулярное множество, то регулярно и

L_{\frac{3}{3}}=\left\{ z \mid (\exists x, y)[\left|x\right|=\left|y\right|=\left|z\right|, x y z \in L]\right\}

?

Пример 2.43

Пусть $A$ и $B$ — два регулярных языка. Покажите, что язык, определённый как

C(A, B)=\left\{ x \in A \mid (\exists y)\left[\left|y\right|=|x|^{2}, y \in B\right]\right\}

также регулярен.

?

Пример 2.44

Покажите, что если $L$ регулярен, то регулярен и

\operatorname {SQRT}(L)=\left\{ x \mid (\exists y)\left[\left|y\right|=|x|^{2}, x y \in L\right]\right\}

?

Задача 2.6.1

(a)(b)

Докажите следующее тождество:

?

(a)

$\operatorname {MAX}(L)=L \backslash \left(L / \Sigma^{+}\right)$ , где $\operatorname {MAX}(L)=\left\{ \boldsymbol {x} \in L \mid \boldsymbol {x}\text{ не является собственным префиксом никакой строки из }L\right\}$ .

(b)

$\operatorname {MIN}(L)=L \backslash \left(L \Sigma^{+}\right)$ .

Задача 2.6.2

(a)(b)(c)

Для любых двух битов $a, b \in \left\{ 0,1\right\}$ , $a \oplus b$ обозначает исключающее ИЛИ $a$ и $b$ ; то есть $0 \oplus 0=1 \oplus 1=0$ и $0 \oplus 1=1 \oplus 0=1$ . Для любых двух двоичных строк $x$ и $y$ с $\left|x\right|=\left|y\right|$ , $x \oplus y$ обозначает поразрядное исключающее ИЛИ строк $x$ и $y$ . Например, если $x=0011$ и $y=0101$ , то $x \oplus y=0110$ . Пусть $A=001(0+1)^{*}$ и $B=(0+1)^{*} 100$ . Найдите регулярное выражение для каждого из следующих языков:

?

(a)

$A \vee B$ .

(b)

$A \oplus B=\left\{ x \oplus y|x \in A, y \in B,|x|=|y|\right\}$ .

(c)

$\left\{ a_{1} b_{1} a_{2} b_{2} \cdots a_{n} b_{n} \mid a_{1} a_{2} \cdots a_{n} \in A, b_{1} b_{2} \cdots b_{n} \in B\right\}$ .

Задача 2.6.3

Покажите, что если $A$ и $B$ — регулярные языки, то регулярны и следующие языки:

?

(a)

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

(b)

$\left\{ x \mid x \in A, x x \in A\right\}$ .

(c)

$A_{x}=\left\{ y \mid x y \in A\right\}$ , где $x$ — фиксированная строка.

(d)

$\left\{ a_{1} a_{2} \cdots a_{2 n} \mid a_{2} a_{1} a_{4} a_{3} \cdots a_{2 n} a_{2 n-1} \in A\right\}$ .

(e)

$\left\{ a_{1} a_{3} \cdots a_{2 n-3} a_{2 n-1} \mid a_{1} a_{2} \cdots a_{2 n} \in A\right\}$ .

(f)

$\left\{ a_{1} b_{1} a_{2} b_{2} \cdots a_{n} b_{n} \mid a_{1} a_{2} \cdots a_{n} \in A, b_{1} b_{2} \cdots b_{n} \in B\right\}$ .

(g)

$A \oplus B$ .

Задача 2.6.4

Приведите альтернативное доказательство примера 2.42, основанное на следующей идее: мы можем моделировать НКА $\bar{M}$ на $x y$ вместе с $\widehat{M}_{i}$ на $z$ , моделируя на каждом шаге два перехода $\bar{M}$ и один переход $\widehat{M}_{i}$ . (Таким образом, новый НКА для $L_{\frac{3}{3}}$ имеет всего $n+2$ дорожки.)

?

Задача 2.6.5

Покажите, что если $A$ и $B$ — регулярные языки, то регулярны и следующие:

?

(a)

$\left\{ x y z \mid z y x \in A\right\}$ .

(b)

$\left\{ x y z \mid z y x \in A, y \in B\right\}$ .

(c)

$\left\{ y \mid (\exists x)[\left|x\right|=\left|y\right|, x y \in A]\right\}$ .

(d)

$\left\{ x \mid (\exists y, z)[\left|x\right|=\left|y\right|=\left|z\right|, x y z \in A]\right\}$ .

(e)

$\left\{ y \mid (\exists x, z),[\left|x\right|=\left|y\right|=\left|z\right|, x y z \in A]\right\}$ .

(f)

$\left\{ y z \mid (\exists x)[\left|x\right|=\left|y\right|=\left|z\right|, x y z \in A]\right\}$ .

(g)

$\left\{ x y \mid (\exists z)[\left|x\right|=\left|y\right|=\left|z\right|, x y z \in A]\right\}$ .

(h)

$\left\{ x \mid (\exists w, y, z)[x=w y z \text{ и } w y^{R} z \in A]\right\}$ .

Задача 2.6.6

Рассмотрим булеву функцию $f\left(a_{1}, a_{2}, \cdots , a_{n}\right)$ . Для любых $n$ двоичных строк $x_{1}, x_{2}, \cdots , x_{n}$ одинаковой длины обозначим через $f\left(x_{1}, x_{2}, \cdots , x_{n}\right)$ поразрядное применение функции $f$ к $x_{1}, x_{2}, \cdots , x_{n}$ . То есть, если $x_{i}=x_{i_{1}} x_{i_{2}} \ldots x_{i_{k}}$ для $i=1,2$ , $\ldots , n$ , где каждый $x_{i_{j}}$ — бит из $\left\{ 0,1\right\}$ , то $f\left(x_{1}, x_{2}, \ldots , x_{n}\right)$ равно

f\left(x_{11}, x_{21}, \ldots , x_{n 1}\right) \cdot f\left(x_{12}, x_{22}, \ldots , x_{n 2}\right) \cdots f\left(x_{1 k}, x_{2 k}, \ldots , x_{n k}\right)

Покажите, что если языки $A_{1}, A_{2}, \cdots , A_{n}$ регулярны, то язык

\begin{aligned} \left\{ f\left(x_{1}, x_{2}, \cdots , x_{n}\right) \mid & \left|x_{1}\right|=\left|x_{2}\right|=\cdots =\left|x_{n}\right| \\ & x_{1} \in A_{1}, x_{2} \in A_{2}, \cdots , x_{n} \in A_{n}\right\} \end{aligned}

также регулярен.

?

Задача 2.6.7

В упражнении 3(c) выше покажите, что для любого регулярного языка $A$ число различных $A_{x}$ конечно. Найдите верхнюю оценку для этого числа, предполагая, что $A$ принимается ДКА с $s$ состояниями.

?

Задача 2.6.8

Верны ли следующие утверждения? Докажите или опровергните ваш ответ.

?

(a)

Если $A$ регулярен и $A \subseteq B$ , то $B$ регулярен.

(b)

Если $A$ регулярен и $B \subseteq A$ , то $B$ регулярен.

(c)

Если $A^{2}$ регулярен, то $A$ регулярен.

(d)

Если $A$ и $A B$ регулярны, то $B$ регулярен.

(e)

Если $A$ и $B$ регулярны, то $\bigcup_{i=0}^{\infty }\left(A^{i} \cap B^{i}\right)$ регулярен.

Задача 2.6.9

Покажите, что каждый регулярный язык в $0^{*}$ можно представить в виде

0^{a_{1}}+0^{a_{2}}+\cdots +0^{a_{k}}+\left(0^{b_{1}}+0^{b_{2}}+\cdots +0^{b_{h}}\right)\left(0^{c}\right)^{*}

для некоторых целочисленных констант $a_{1}, a_{2}, \cdots , a_{k}, b_{1}, b_{2}, \cdots , b_{h}$ и $c$ .

?

Задача 2.6.10

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

Подмножество $P$ неотрицательных целых чисел является в конечном счёте периодическим, если существуют два положительных целых числа $b, p$ , такие что для всех $m \geq b$ из $m \in P$ следует $m+p \in P$ . Докажите следующие утверждения:

?

(a)

Для любого регулярного языка $L$ множество $\left\{ \left|x\right| \mid x \in L\right\}$ в конечном счёте периодическое.

(b)

Язык $L$ над $\left\{ 0\right\}$ регулярен тогда и только тогда, когда $\left\{ \left|x\right| \mid x \in L\right\}$ в конечном счёте периодическое.

(c)

Если $f$ — отображение из целых чисел в целые числа, такое что $f^{-1}(P)$ в конечном счёте периодическое для каждого в конечном счёте периодического множества $P$ , то множество $\left\{ x \in A \mid (\exists y)[\left|y\right|=f(\left|x\right|), y \in B]\right\}$ регулярно для любой пары регулярных множеств $A$ и $B$ .

(d)

Если $f$ — отображение из целых чисел в целые числа, такое что $f^{-1}(P)$ в конечном счёте периодическое для каждого в конечном счёте периодического множества $P$ , то множество $\left\{ x \mid (\exists y)[\left|y\right|=f(\left|x\right|), x y \in L\right\}$ регулярно для любого регулярного множества $L$ .

Задача 2.6.11

(a)(b)

Примените упражнение 10(d) выше, чтобы доказать следующие результаты:

?

(a)

Если $L$ — регулярный язык, то регулярен и $\left\{ x \mid (\exists y)[\left|y\right|=2^{\left|x\right|}, x y \in L]\right\}$ . [Подсказка: используйте теорему Ферма, которая утверждает, что для любого нечётного целого числа $m \geq 3$ существует целое число $\varphi (m)$ , такое что $2^{\varphi (m)} \equiv 1 \bmod m$ .]

(b)

Если $L$ — регулярный язык, то регулярен и $\left\{ x \mid (\exists y)[|y|^{2}=\left|x\right|, x y \in L]\right\}$ .

Свойства замкнутости регулярных языков