ДЗ: Курс Основы теории вычислительных систем 1/1 (ИДДО ОТВС-Б-3-1-ЗаО). КМ-3. Расчетные задания. Варианты 1-8 вариант 2

Задания:

1) Задан автомат Мили в виде графа. Построить совмещенную таблицу переходов/выходов. Найти эквивалентный ему автомат Мура, построить граф и отмеченную таблицу переходов.
2) Записать событие, состоящее из всех слов алфавита x' = {x₁, x₂, x₃}, которые начинаются буквами x₁, x₃, а заканчиваются отрезком x₁ или x₃ . Представить выражение в виде графа.
3) Представить в виде графа регулярное выражение {c V d}^* * ({b V a}^* V a) V b * d
4) Составить регулярные выражения для следующего автомата А. На вход А поступают 4х-разрядные двоичные числа – тетрады. Тетрады являются правильными, если они меньше 10, остальные – неправильные. При поступлении на вход автомата любой правильной тетрады на выходе формируется сигнал y₂, при поступлении любой неправильной – сигнал y₁.
5) Построить автомат по продаже билетов стоимостью 6 руб. Автомат может принимать монеты 1, 2, 5 руб. Сдачу автомат не выдает. При вводе неверной суммы – сброс денег. Использовать синтез по регулярным выражениям.
6) Провести структурный синтез по графу автомата.

Пример: