Конечные автоматы: преобразователи и распознаватели

Конечный преобразователь $\mathfrak {M}=\left(Q, \Sigma , \Omega , P_{1}, q_{0}\right)$ определён так: $Q=\left\{ q_{0}, q_{1}, q_{2}, q_{3}\right\} , \Sigma =\left\{ 0,1\right\} , \Omega =\left\{ A, P, T\right\}$, а программа $P_{1}$ задана таблицей на рис. 23.

Конечный преобразователь $\mathfrak {M}_{c}=\left(Q, \Sigma , \Omega , P_{2}, q_{0}\right)$ задан следующим образом: $Q=\left\{ q_{0}, q_{1}, q_{2}, q_{3}\right\} , \Sigma =\left\{ 0,1\right\} , \Omega =\left\{ 0,1\right\}$, а программа $P_{2}$ задана таблицей на рис. 23. Этот преобразователь вычитает из входного числа $x$ в двоичной записи некоторую константу $c$, то есть выдаёт при $c \leqslant x$ выходное число $y=x-c$ в двоичной записи. Чему равна эта константа $c$? Разряды в двоичной записи чисел идут от младших к старшим, то есть число десять выглядит так: 0101.

Автомат по размену монет имеет щель для приёма монет и накопитель для их выдачи. Автомат принимает монеты достоинством в 1,2 и 10 рублей и разменивает их монетами по 5 рублей. При этом на табло отображается уже внесённая сумма, а как только сумма оказывается достаточной, автомат сразу же выдаёт пятирублёвые монеты в нужном количестве.

Построить конечный преобразователь, моделирующий работу этого автомата. Определить входной и выходной алфавиты и построить его программу.

Торговый автомат по продаже кофе имеет щель для получения монет, кнопку, нажатие которой после уплаты достаточной суммы приводит к получению кофе, и накопитель, через который он выдаёт сдачу покупателю. Автомат принимает монеты достоинством в 1, 2 и 5 рублей. Чашка кофе стоит 8 рублей. Пока полученная сумма недостаточна, горит красная лампочка. Если сумма, полученная автоматом, становится больше или равна 8 рублям, то зажигается зелёная лампочка и после нажатия кнопки автомат наливает кофе и, если требуется, выдаёт сдачу наименьшим количеством монет. Если автомат получает монету, когда горит зелёная лампочка, то он немедленно её возвращает.

Построить конечный преобразователь, моделирующий работу этого автомата. Определить входной и выходной алфавиты и построить его программу.

Электронные часы имеют табло с указанием часов, минут и секунд, а также — две управляющие кнопки. Первая кнопка переводит часы из нормального режима в режим настройки времени — сначала в настройку часов, затем — минут, затем — секунд, а затем возвращает в нормальный режим. Вторая кнопка в нормальном режиме ничего не меняет, а в режиме настройки её нажатие увеличивает на единицу число настраиваемых часов, минут или секунд соответственно.

Построить конечный преобразователь, который моделирует работу часов. На вход он принимает сигналы нажатия от двух кнопок, а на выходе выдаёт сигналы изменения режима и увеличения соответствующего числа. Изобразить диаграмму преобразователя.

Рис. 24: Программы автоматов из задач 439, 440 и 441.

Построить конечный преобразователь, умножающий число в двоичной записи на 3. Цифры записаны в порядке возрастания разрядов (как в задаче 432 на стр. 129).

Построить конечный преобразователь, нацело делящий число в десятичной записи на 3. Цифры записаны в порядке убывания разрядов (в «обычном» порядке).

Определить, какие языки могут распознавать детерминированные конечные автоматы с алфавитом $\Sigma =\left\{ 0,1\right\}$ и множеством состояний $Q=\left\{ q_{0}, q_{1}\right\}$.

Пусть $\Sigma =\left\{ a, b\right\} , Q=\left\{ q_{0}, q_{1}, q_{2}, q_{3}, q_{4}, q_{5}\right\} , F=\left\{ q_{3}, q_{4}\right\}$ и функция переходов $P_{1}$ конечного автомата $\mathfrak {M}=\left(Q, \Sigma , P_{1}, q_{0}, F\right)$ задана таблицей, представленной на рис. 24. Определить, какие из следующих трёх слов распознаются автоматом $\mathfrak {M}: w=a a a b b a b a b, v=b a b b b a b b a$, $u=a b a b a a a b?$

Язык $L$ состоит из всех слов, которые начинаются с буквы $b$ и содержат количество букв $a$, кратное трём. Определить, какие из следующих трёх детерминированных конечных автоматов распознают язык $L: \mathfrak {M}_{i}=\left(\left\{ q_{0}, q_{1}, q_{2}, q_{3}, q_{4}\right\} ,\left\{ a, b\right\} , P_{i}, q_{0},\left\{ q_{1}\right\} \right), i=2,3,4$, программы $P_{i}$ заданы таблицей, изображённой на рис. 24.

Составляющие конечного автомата $\mathfrak {M}=\left(Q, \Sigma , P_{5}, q_{0}, F\right)$ равны $Q=\left\{ q_{0}, q_{1}, q_{2}, q_{3}\right\} , \Sigma =\left\{ a, b\right\} , F=\left\{ q_{3}\right\}$, а программа $P_{5}$ задаётся таблицей на рис. 24. Доказать, что автомат $\mathfrak {M}$ распознаёт язык, состоя-

щий в точности из тех слов в алфавите $\left\{ a, b\right\}$, которые заканчиваются фрагментом $a b a$.

Доказать, что приведённый на рис. 25 автомат, распознаёт язык, состоящий из всех слов, заканчивающихся на $b a$ и не содержащих при этом $a a$.

Рис. 25: Автомат из задачи 442.

Индукцией по длине слова $w$ доказать следующее утверждение: $(q, w x) \vdash_{\mathfrak {M}}^{*}(p, x)$ тогда и только тогда, когда в $\mathfrak {D}_{\mathfrak {M}}$ есть путь из $q$ в $p$, несущий $w$.

Построить детерминированные конечные автоматы, которые распознают следующие языки в алфавите $\Sigma =\left\{ a, b\right\}$ :

Построить детерминированный конечный автомат, который проверяет правильность сложения. На вход поступают «трёхэтажные» символы, в которых на верхнем этаже записан разряд первого слагаемого, на среднем — второго, на нижнем — предполагаемой суммы. Автомат должен принять слово, если записанный на нижнем этаже результат сложения верен. Цифры всех чисел записаны в порядке возрастания разрядов.

Построить детерминированные конечные автоматы, распознающие следующие языки в алфавите $\left\{ 0,1\right\}$ :

Построить детерминированный конечный автомат $\mathfrak {M}$ с алфавитом $\Sigma =\left\{ \wedge , \vee , 0,1\right\}$, который принимает только те слова, которые являются истинными ДНФ.

Даны два языка в алфавите $\Sigma =\left\{ a, b\right\}$ :

Дан $\mathfrak {M}=(Q, \Sigma , P, q,\left\{ p\right\} )$ — недетерминированный конечный автомат, где $Q=\left\{ q, p, s\right\} , \Sigma =\left\{ 0,1\right\} , P=\left\{ q, 0 \rightarrow p ; q, 0 \rightarrow s ; q, 1 \rightarrow q ; p, 0 \rightarrow q ; p, 0 \rightarrow p ; s, 1 \rightarrow q ; s, 1 \rightarrow p\right\}$.

Определить, какие из следующих трёх детерминированных автоматов $\mathfrak {M}_{i}=\left(Q_{i}, \Sigma , P_{i}, q, F_{i}\right)$ эквивалентны $\mathfrak {M}$ :

Используя процедуру детерминизации, построить детерминированные автоматы, эквивалентные следующим недетерминированным конечным автоматам $\mathfrak {N}$ с алфавитом $\Sigma =\left\{ a, b\right\}$ :

Пусть $\mathfrak {M}=\left(Q, \Sigma , P, q_{0}, F\right)$ — это недетерминированный конечный автомат, в котором $Q=\left\{ q_{0}, q_{1}, q_{2}, q_{3}\right\} , \Sigma =\left\{ a, b\right\} , F=\left\{ q_{1}, q_{3}\right\}$, $P=\left\{ q_{0}, a \rightarrow q_{0} ; q_{0}, a \rightarrow q_{1} ; q_{0}, b \rightarrow q_{2} ; q_{1}, b \rightarrow q_{0} ; q_{2}, a \rightarrow q_{0} ; q_{2}, a \rightarrow q_{3} ; q_{2}, b \rightarrow q_{1} ; q_{2}, b \rightarrow q_{2} ; q_{2}, b \rightarrow q_{3} ; q_{3}, a \rightarrow q_{0} ; q_{3}, a \rightarrow q_{3}\right\}$.

Дан $\mathfrak {M}=\left(Q, \Sigma , P, q_{0}, F\right)$ — недетерминированный конечный автомат, где $Q=\left\{ q_{0}, q_{1}, q_{2}, q_{3}, q_{4}, q_{5}\right\} , \Sigma =\left\{ 0,1\right\} , F=\left\{ q_{5}\right\}$, а $P$ определена в таблице на рис. 26 на противоположной странице (означает отсутствие соответствующих переходов).

Применить процедуру детерминизации и построить детерминированный автомат эквивалентный недетерминированному конечному автомату, изображённому на рис. 27.

Рис. 27: Автомат из задачи 453.

Язык $L$ в алфавите $\Sigma =\left\{ a_{1}, \ldots , a_{k}\right\}$ состоит из всех слов, в которых отсутствует хотя бы одна буква алфавита $\Sigma$.

Недетерминированный конечный автомат $\mathfrak {N}=\left(Q, \Sigma , P, q_{0}, F\right)$ для алфавита $\Sigma =\left\{ a, b, c\right\}$ с $n$ состояниями $Q=\left\{ q_{0}, q_{1}, \ldots , q_{n-1}\right\}$ и множеством принимающих состояний $F=\left\{ q_{0}\right\}$ изображён на рис. 28.

Рис. 28: Автомат из задачи 455.

Пусть $\mathfrak {M}=\left(\mathrm{P}(Q), \Sigma , P^{\prime },\left\{ q_{0}\right\} , F^{\prime }\right)$ — это автомат, полученный из $\mathfrak {N}$ при помощи процедуры детерминизации. Доказать, что