Основы правозащитной деятельности (Задачи к ГОСам) (Решение → 4540)

4 работы + ответы на билет. Варианты заданий смотри в файлах.

<u>Задача 1.</u> <u>Записать событие, состоящее из всех слов алфавита,</u> которые начинаются буквами или и и или, а заканчиваются отрезком или . Представить выражение в виде графа.

<u>Задача 2.</u> Представить в виде графа регулярное выражение

<u>Задача 3.</u> Записать событие, состоящее из всех слов алфавита, не содержащее комбинации букв и оканчивающееся на <img src="//:0" height="24" width="17">.

<u>Задача 4.</u> Составить регулярные выражения для следующего автомата А. На вход А поступают 4х-разрядные двоичные числа – тетрады. Тетрады являются правильными, если они меньше 10, остальные – неправильные. При поступлении на вход автомата любой правильной тетрады на выходе формируется сигнал <img src="//:0" height="23" width="17">, при поступлении любой неправильной – сигнал .

<u>Задача 5.</u> Синтезировать автомат по продаже билетов стоимостью 6руб. Автомат может принимать монеты 1,2,5 руб. Сдачу автомат не выдает. При вводе неверной сумы – сброс денег обратно.

1. Синтезировать автомат по продаже билетов стоимостью 7 руб. Автомат может принимать монеты 1, 2, 5 руб. Для синтеза использовать безусловный кратный эксперимент.

2. Расшифровать данный автомат по результатам условного кратного эксперимента.

* помечено начальное состояние.

3. Построить автомат Мили, исходя из заданного дерева управления, представляющего результат кратного эксперимента.

1. Провести структурный синтез по графу автомата.

2. Провести структурный синтез по графу автомата.

<u>Задача 1.</u> Построить МТ для преобразования двоичного числа со знаком в обратный код. Алфавит для х ={0,1}, т.е. х это число в троичном коде. Например, х = 1,1010. Результат R=1,0101.

<u>Задача 2. </u>Построить МТ для однократного копирования любого слова в алфавите {a,b,c}. Например дано слово S=aacabbccaba. Надо получить SS= aacabbccaba aacabbccaba.

<u>Задача 3.</u> Построить НАМ для перевода числа x из унарной системы в двоичную. Алфавит для х ={|}, т.е. х это число в унарном коде. Например, х = |||||. Результат R=101.

<u>Задача 4.</u> Построить НАМ для определения симметрии слова. Алфавит А={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