Основы теории вычислительных систем 4 задания и ответы на билет

Варианты задач смотри в файлах.

Перевести подбором коэффициентов многочлена

Перевести делением на основание

Перевести делением и умножением на основание

Перевести с использованием промежуточной системы счисления.

4 задание:

1. Задан автомат Мура в виде графа. Построить отмеченную таблицу переходов. Найти эквивалентный ему автомат Мили, построить граф и совмещенную таблицу переходов/выходов.

2. Задан автомат Мили в виде графа. Построить совмещенную таблицу переходов/выходов. Найти эквивалентный ему автомат Мура, построить граф и отмеченную таблицу переходов.

Вопросы билета:

1. Регулярные выражения и их графовая интерпретация.

2. Эксперименты над автоматами: типизация; основные понятия.

3. Построить машину Тьюринга для однократного копирования любого слова в алфавите {a,b,c}.