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

Пример 2.23

Дан НКА $M=\left(Q,\left\{ 0,1\right\} , \delta , q_{0}, F\right)$ , где $Q=\left\{ q_{0}, q_{1}, q_{2}\text{, }q_{3}, q_{4}, q_{5}\right\} , F=\left\{ q_{3}, q_{4}\right\}$ , и

$\delta$	0	1	$\varepsilon$
$q_{0}$	$\left\{ q_{0}\right\}$	$\left\{ q_{0}, q_{2}\right\}$	$\left\{ q_{1}\right\}$
$q_{1}$	$\left\{ q_{5}\right\}$	$\left\{ q_{2}\right\}$	-
$q_{2}$	$\left\{ q_{3}\right\}$	-	-
$q_{3}$	-	-	$\left\{ q_{4}\right\}$
$q_{4}$	$\left\{ q_{3}\right\}$	-	-
$q_{5}$	-	$\left\{ q_{4}\right\}$	-

(Диаграмма переходов $M$ показана на рисунке 2.29(a).) Найдите ДКА, эквивалентный НКА $M$ .

Рисунок 2.29: Преобразование НКА в ДКА.

?

Пример 2.24

Постройте ДКА, эквивалентный НКА $M=(\left\{ p, q\text{, }r\right\} ,\left\{ 0,1\right\} , \delta , p,\left\{ q, r\right\} )$ , где

$\delta$	0	1
$p$	$\left\{ p, q\right\}$	$\left\{ p\right\}$
$q$	-	$\left\{ r\right\}$
$r$	-	-

?

Пример 2.26

Пусть $M=(\left\{ p, q, r, s\right\} ,\left\{ 0,1\right\} , \delta , p,\left\{ q, s\right\} )$ — $N F A$ , заданный

$\delta$	0	1
$p$	$\left\{ q, s\right\}$	$\left\{ q\right\}$
$q$	$\left\{ r\right\}$	$\left\{ q, r\right\}$
$r$	$\left\{ s\right\}$	$\left\{ p\right\}$
$s$	-	$\left\{ p\right\}$

Постройте НКА, принимающий $\overline{L(M)}$ .

?

Пример 2.27

Постройте ДКА, принимающий множество всех двоичных строк, у которых пятый символ справа равен 0.

?

Пример 2.28

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

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

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

\begin{aligned} \operatorname {value}(w) & =((a \times b) \times c) \times b=(a \times c) \times b=b \times b=c, \text{ and } \\ \operatorname {value}\left(w^{R}\right) & =((b \times c) \times b) \times a=(a \times b) \times a=a \times a=c. \end{aligned}

Постройте НКА для множества $L$ всех строк $w$ над $\left\{ a, b, c\right\}$ таких, что $\operatorname {value}(w)=\operatorname {value}\left(w^{R}\right)$ . (Например, $a b c b \in L$ , а $a b b \notin L$ .)

?

Задача 2.4.1

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

Преобразуйте каждый из следующих НКА в эквивалентный ДКА:

?

(a)

НКА $M=(\left\{ p, q, r\right\} ,,\left\{ 0,1\right\} , \delta , p,\left\{ q, r\right\} )$ , где

$\delta$	0	1
$p$	$\left\{ p\right\}$	$\left\{ p, q\right\}$
$q$	$\left\{ r\right\}$	-
$r$	-	-

(b)

НКА $M$ на рисунке 2.27(a).

(c)

НКА $M$ на рисунке 2.27(b).

(d)

НКА $M$ на рисунке 2.27(c).

Задача 2.4.2

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

Для каждого из следующих языков постройте ДКА, принимающий этот язык:

?

(a)

Множество двоичных строк, содержащих одновременно подстроку 010 и подстроку 101.

(b)

Множество всех двоичных строк, заканчивающихся на 00, 01 или 10.

(c)

Множество двоичных строк, содержащих в качестве подстрок и 001, и 110, либо не содержащих ни 001, ни 110.

(d)

Множество двоичных строк, у которых и четвёртый символ справа, и четвёртый символ слева равны 0. [Примечание: обе строки 0110 и 10101 принадлежат этому множеству.]

Задача 2.4.3

(a)(b)(c)

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

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

Постройте НКА для следующих языков:

?

(a)

$\left\{ x \mid \operatorname {value}(x) \neq \operatorname {value}\left(x^{R}\right)\right\}$ .

(b)

$\left\{ x y \mid \operatorname {value}(x)=\operatorname {value}\left(y^{R}\right)\right\}$ .

(c)

$\left\{ x y \mid \operatorname {value}(x)=\operatorname {value}(y)\right\}$ .