Конечные автоматы

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

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

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

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

Построить конечный преобразователь, умножающий число в двоичной записи на 3. Разряды в двоичной записи чисел идут от младших к старшим, то есть число десять выглядит так: 0101.

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

Доказать предложение 93 на стр. 286.

Предложение 93: для конечного преобразователя $\mathfrak {M}$, его конфигурации $\sigma$ и натурального числа $k$ существует не более одной конфигурации $\tau$ такой, что $\sigma \vdash_{\mathfrak {M}}^{k} \tau$.

Доказать, что приведённый на рис. 83 на стр. 307 автомат $\mathfrak {M}$ распознаёт язык, состоящий из всех слов, заканчивающихся на «aba».

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

Лемма 96: автомат $\mathfrak {M}$ принимает слово $w$ тогда и только тогда, когда в диаграмме $\mathfrak {D}_{\mathfrak {M}}$ есть несущий $w$ путь из начального состояния $q_{0}$ в некоторое принимающее состояние $q \in F$, то есть $w$ переводит $q_{0}$ в принимающее состояние $q$.

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

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

Доказать лемму 97 на стр. 297.

Определение 126 (Произведение автоматов). Пусть даны два конечных автомата $\mathfrak {M}_{1}=(Q_{1}, \Sigma , P_{1}, q_{0}^{1}, F_{1})$ и $\mathfrak {M}_{2}=(Q_{2}, \Sigma , P_{2}, q_{0}^{2}, F_{2})$ с общим входным алфавитом $\Sigma$. Произведением автоматов $\mathfrak {M}_{1}$ и $\mathfrak {M}_{2}$ называется всякий автомат $\mathfrak {N}$ следующего вида: $\mathfrak {N}=(Q_{1} \times Q_{2}, \Sigma , P, (q_{0}^{1}, q_{0}^{2}), F)$, в котором программа $P$ содержит команду $(q_{1}, q_{2}), a \rightarrow (p_{1}, p_{2})$, если $q_{1}, a \rightarrow p_{1} \in P_{1}$ и $q_{2}, a \rightarrow p_{2} \in P_{2}$. (На множество принимающих состояний $F$ автомата $\mathfrak {N}$ никаких условий не накладывается, поэтому произведение не является однозначно определённой операцией — в зависимости от $F$ получаются разные автоматы.)

Лемма 97: если $\mathfrak {N}$ — произведение $\mathfrak {M}_{1}$ и $\mathfrak {M}_{2}$, то для любых двух состояний $(q_{1}, q_{2})$ и $(p_{1}, p_{2})$ автомата $\mathfrak {N}$ и любого входного слова $w$ выполнено следующее: $w$ переводит $(q_{1}, q_{2})$ в $(p_{1}, p_{2})$ в автомате $\mathfrak {N}$ в том и только том случае, когда $w$ одновременно переводит $q_{1}$ в $p_{1}$ в автомате $\mathfrak {M}_{1}$ и $q_{2}$ в $p_{2}$ в автомате $\mathfrak {M}_{2}$.

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

Недетерминированный конечный автомат $\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\}$ изображён на рис. 85 на следующей странице. Пусть $\mathfrak {M}=\left(\mathrm{P}(Q), \Sigma , P^{\prime },\left\{ q_{0}\right\} , F^{\prime }\right)$ — это автомат, полученный из $\mathfrak {N}$ при помощи процедуры детерминизации. Доказать, что

Рис. 85. Автомат из задачи 246.