Основы теории вычислительных систем 4 задания и ответы на билет
4 работы + ответы на билет. Варианты заданий смотри в файлах.
Задача 1. Записать событие, состоящее из всех слов алфавита, которые начинаются буквами или и и или, а заканчиваются отрезком или . Представить выражение в виде графа.
Задача 2. Представить в виде графа регулярное выражение
Задача 3. Записать событие, состоящее из всех слов алфавита, не содержащее комбинации букв и оканчивающееся на .
Задача 4. Составить регулярные выражения для следующего автомата А. На вход А поступают 4х-разрядные двоичные числа – тетрады. Тетрады являются правильными, если они меньше 10, остальные – неправильные. При поступлении на вход автомата любой правильной тетрады на выходе формируется сигнал , при поступлении любой неправильной – сигнал .
Задача 5. Синтезировать автомат по продаже билетов стоимостью 6руб. Автомат может принимать монеты 1,2,5 руб. Сдачу автомат не выдает. При вводе неверной сумы – сброс денег обратно.
- Синтезировать автомат по продаже билетов стоимостью 7 руб. Автомат может принимать монеты 1, 2, 5 руб. Для синтеза использовать безусловный кратный эксперимент.
2. Расшифровать данный автомат по результатам условного кратного эксперимента.
* помечено начальное состояние.
3. Построить автомат Мили, исходя из заданного дерева управления, представляющего результат кратного эксперимента.
1. Провести структурный синтез по графу автомата.
2. Провести структурный синтез по графу автомата.
Задача 1. Построить МТ для преобразования двоичного числа со знаком в обратный код. Алфавит для х ={0,1}, т.е. х это число в троичном коде. Например, х = 1,1010. Результат R=1,0101.
Задача 2. Построить МТ для однократного копирования любого слова в алфавите {a,b,c}. Например дано слово S=aacabbccaba. Надо получить SS= aacabbccaba aacabbccaba.
Задача 3. Построить НАМ для перевода числа x из унарной системы в двоичную. Алфавит для х ={|}, т.е. х это число в унарном коде. Например, х = |||||. Результат R=101.
Задача 4. Построить НАМ для определения симметрии слова. Алфавит А={a,b}. Слово может быть любым. Алгоритм должен быть универсальным.
Например S=aababaa. Слово симметрично относительно а. Или S=aabbaa – слово также симметрично. А S=abaabaa – нет симметрии в слове.
Вопросы билета:
1. Автоматные операторы Мили (G.H. Mealy) и Мура (E.F.Moore). Основной способ задания конечных автоматов.
2. Алгоритмические системы. Машины Поста (E.L.Post) и Тьюринга (A.Turing) как автоматы с бесконечной памятью
3. Построить логическую схему тренажера, предназначенного для обучения операторов работе на пульте. Пульт имеет 4 кнопки k1 k2 k3 k4, которые должны включаться в строго определенной последовательности. При правильном нажатии кнопок вырабатывается сигнал W, при неправильном — сигнал N. По окончании сеанса схема должна автоматически устанавливаться в начальное состояние.
Правильная последовательность: k3k2k1k1k4
