Автомат по продаже кофе имеет

Задача 4.1. Автомат по продаже кофе имеет щель для получения монет, кнопку, нажатие которой после уплаты достаточной суммы приводит к получению кофе, и накопитель, через который он выдает сдачу покупателю. Автомат принимает монеты достоинством в 1, 2 и 5 рублей. Чашка кофе стоит 8 руб. Пока полученная сумма недостаточна, горит красная лампочка. Если сумма, полученная автоматом, 8, то зажигается зеленая лампочка и после нажатия кнопки автомат наливает кофе и, если требуется, дает сдачу. Если автомат получает монету, когда горит зеленая лампочка, то он немедленно ее возвращает. Определите входной и выходной алфавиты конечного автомата, управляющего продажей кофе, и постройте его функции переходов и выходов.
Задача 4.2. Электронные часы имеют табло с указанием часов, минут и секунд и две управляющие кнопки. Одна кнопка переводит часы из нормального режима в режим настройки времени - вначале в настройку часов, затем - минут, затем - секунд, а затем возвращает в нормальный режим. Другая кнопка в нормальном режиме ничего не меняет, а в режиме настройки нажатие на нее увеличивает на единицу число настраеваемых часов, минут или секунд. Постройте автомат, который принимает на вход сигналы нажатия от двух кнопок, а на выходе выдает сигналы изменения режима и увеличения соответствующего числа.
Задача 4.3. Докажите лемму 4.1 индукцией по длине входного слова.
Задача 4.4. Постройте детерминированные конечные автоматы, которые распознают следующие языки в алфавите ?={a, b}:

• L = {w | длина w делится на 5};
• L = {w | w не содержит подслов 'aab' и 'bba'};
• L = {w | w содержит четное число букв а и нечетное число букв b};
• L = {w | число букв а делится на 3, а число букв b на 2 }.

Задача 4.5. Выше в примере 4.1 был построен автомат с выходом, выполняющий сложение двух двоичных чисел. Постройте автомат-распознаватель, который проверяет правильность сложения. На вход поступают последовательности троек нулей и единиц:

Автомат должен допустить такую последовательность, если y = y(n) … y(2)y(1) - это первые n битов суммы двоичных чисел x1= x1(n)… x1(2)x1(1) и x2 = x2(n)… x2(2)x2(1).


Задача 4.7. Докажите лемму 4.2.
Задача 4.8. Докажите, что приведенный на рис. 4.5 автомат A распознает язык, состоящий из всех слов, заканчивающихся на 'aba'.
Задача 4.9. Используя процедуру детерминизации недетерминированных автоматов из теоремы 4.2, постройте ДКА, эквивалентный заданному НКА M.

• M=<{a, b},{0, 1,2}, 0,{2}, ?> с программой ?: 0a
  
  1, 0
  
  1, 1b
  
  2, 1
  
  2, 2 b
  
  2.
• M=<{a, b},{0, 1,2}, 0,{2}, ?> с программой ?: 0a
  
  1, 0a
  
  2, 1b
  
  2, 1
  
  2, 2 b
  
  0.

Содержание раздела

---