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

Пример 2.17

Найдите НКА, принимающий множество двоичных строк, содержащих подстроку 010.

?

Пример 2.18

Найдите НКА, принимающий множество двоичных строк, начинающихся с 010 или заканчивающихся на 110.

?

Пример 2.19

Найдите НКА, принимающий множество двоичных строк, содержащих не менее двух вхождений подстроки 01 и заканчивающихся на 11.

Рисунок 2.22: Решение примера 2.19.

?

Пример 2.20

Найдите НКА, принимающий множество $\left\{ 0^{n} 10^{m} \mid n, m \geq 0, n \equiv m(\bmod 5)\right\}$ .

?

Пример 2.21

Пусть $M_{1}$ и $M_{2}$ — два НКА. Постройте НКА $M$ такой, что $L(M)=L\left(M_{1}\right) \cdot L\left(M_{2}\right)$ .

?

Пример 2.22

Пусть $M_{1}$ — НКА. Постройте НКА $M$ такой, что $L(M)= L\left(M_{1}\right)^{*}$ .

?

Задача 2.3.1

(a)(b)(c)

Рассмотрим НКА $M$ на рисунке 2.26.

?

(a)

Чему равны $\varepsilon$ -замыкание $\left(\left\{ q_{0}\right\} \right)$ и $\varepsilon$ -замыкание $\left(\left\{ q_{1}, q_{2}, q_{3}\right\} \right)$ ?

(b)

Чему равны $\delta \left(\left\{ q_{0}\right\} , 0\right)$ и $\delta \left(\left\{ q_{2}, q_{3}\right\} , 1\right)$ ?

(c)

Постройте деревья вычислений $M$ на строках $x=011$ и $y=101$ . Принимает ли $M$ строки $x$ и $y$ , или отвергает их?

Рисунок 2.26: НКА из упражнения 1.

Задача 2.3.2

Для каждого НКА $M$ , показанного на рисунке 2.27, определите, чему равен $L(M)$ .

?

Задача 2.3.3

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

?

(a)

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

(b)

Множество двоичных строк, содержащих одновременно подстроки 010 и 101. [Подсказка: это эквивалентно множеству двоичных строк, содержащих подстроку 0101, либо подстроку 1010, либо подстроку 010, за которой следует 101, либо подстроку 101, за которой следует 010.]

(c)

Множество двоичных строк, содержащих подстроку 010 либо подстроку 101 и заканчивающихся на 111 или 000.

(d)

Множество двоичных строк, у которых $(3 n)$ -й символ равен 0 для каждого $n \geq 1$ .

(e)

Множество двоичных строк $x$ длины $3 n$ для некоторого $n \geq 1$ , таких что для каждого $1 \leq k \leq n$ хотя бы один из $(3 k-2)$ -го, $(3 k-1)$ -го и $(3 k)$ -го символов $x$ равен 0.

(f)

Множество $\left\{ 0^{n} 10^{m} 10^{q} \mid q \equiv n m(\bmod 5)\right\}$ .

Рисунок 2.27: Три НКА из упражнения 2.

Задача 2.3.4

Докажите, что новое начальное состояние $s$ и заключительное состояние $f$ в построении примера 2.22 необходимы. То есть найдите НКА $M_{1}$ и $M_{2}$ такие, что НКА $M_{1}^{\prime }$ и $M_{2}^{\prime }$ на рисунке 2.28 обладают свойством $L\left(M_{1}^{\prime }\right) \neq L\left(M_{1}\right)^{*}$ и $L\left(M_{2}^{\prime }\right) \neq L\left(M_{2}\right)^{*}$ .

?

Недетерминированные конечные автоматы