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

Пример 2.1

Рассмотрим ДКА $M=\left(Q, \Sigma , \delta , q_{0}, F\right)$ , где $Q=\left\{ q_{0}, q_{1}, q_{2}\text{, }q_{3}\right\} , \Sigma =\left\{ 0,1\right\} , F=\left\{ q_{1}, q_{2}\right\}$ , а $\delta$ — функция, заданная следующей таблицей:

$\delta$	0	1
$q_{0}$	$q_{1}$	$q_{3}$
$q_{1}$	$q_{2}$	$q_{3}$
$q_{2}$	$q_{2}$	$q_{2}$
$q_{3}$	$q_{3}$	$q_{3}$

Начертите диаграмму переходов $M$ .

?

Пример 2.2

Рассмотрим ДКА $M$ , заданный на рисунке 2.2. Определите, принимает ли $M$ строки 000 и 010.

?

Пример 2.3

Какой язык $L(M)$ принимается ДКА $M$ на рисунке 2.2?

?

Пример 2.4

Какой язык $L(M)$ принимается ДКА $M$ на рисунке 2.3?

?

Пример 2.5

Какой язык $L(M)$ принимается ДКА $M$ на рисунке 2.4?

?

Задача 2.1.1

(a)(b)(c)

Рассмотрим ДКА $M$ с диаграммой переходов на рисунке 2.5.

?

(a)

Какое состояние является начальным состоянием $M$ , и какие состояния являются заключительными состояниями $M$ ?

(b)

Для каждой из строк 0001, 010101 и 001110101101 найдите вычислительный путь $M$ на этой строке и определите, принимает ли её $M$ .

(c)

Среди всех строк из (01)*, какие из них принадлежат $L(M)$ ?

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

Задача 2.1.2

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

Для целых чисел $n, d \geq 1$ рассмотрим ДКА $M_{n, d}=\left(Q, \Sigma , \delta , q_{0}, F\right)$ , где $Q= \left\{ q_{0}, q_{1}, q_{2}, \cdots , q_{n-1}\right\} , \Sigma =\left\{ a_{0}, a_{1}, \cdots , a_{d-1}\right\} , \delta \left(q_{i}, a_{k}\right)=q_{(d i+k) \bmod n}$ , а $F=\left\{ q_{1}\right\}$ .

?

(a)

Начертите диаграмму переходов $M_{n, d}$ при $n=7$ и $d=2$ .

(b)

Пусть $n=7, d=2, a_{0}=0$ и $a_{1}=1$ . Найдите $\delta \left(q_{3}, 0101\right)$ и $\delta \left(q_{1}, 11010\right)$ .

(c)

Пусть $n=7, d=2, a_{0}=0$ и $a_{1}=1$ . Найдите двоичные строки $x$ и $y$ такие, что $\delta \left(q_{0}, x\right)=q_{5}$ и $\delta \left(q_{0}, y\right)=q_{6}$ .

(d)

Покажите, что для любого состояния $q_{j} \in Q$ существует строка $x \in \Sigma^{*}$ такая, что $\delta \left(q_{0}, x\right)=q_{j}$ .

Рисунок 2.6: Три ДКА из упражнения 3.

Задача 2.1.3

Для каждого из ДКА $M_{1}, M_{2}$ и $M_{3}$ , показанных на рисунке 2.6(a), (b) и (c) соответственно, опишите словами язык, принимаемый им.

?

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