4.2. Задачи синтеза автоматов

Задача синтеза автоматов состоит в построении автомата с наперед заданным поведением или функционированием.

Примеры выполнения заданий

1. Постройте конечный автомат, воспринимающий на входе двоичную последовательность и выдающий на выходе специальный символ ‘ *’, если во входной последовательности подряд встретится 4 единицы. В остальных случаях автомат на выходе повторяет входной символ.

Решение.

2. Постройте конечный автомат таблично, представляющий двоичный сумматор последовательного действия.

Решение. Обозначим через q₀ и q₁ его состояния, соответствующие отсутствию и наличию переноса.

Задания для самостоятельного выполнения

4.2.1. Постройте конечный автомат, выдающий на выходе символ “!”, всякий раз, когда во входной двоичной последовательности встречается:

1. последовательность 0000;

2. последовательность 1111;

3. последовательность 0110;

4. последовательность 0111;

5. последовательность 1000;

6. последовательность 0011;

7. последовательность 0010;

8. последовательность 1110;

9. последовательность 0001;

10. последовательность 1100.

4.2.2. Постройте конечный автомат, выдающий на выходе символ “♫”, всякий раз, когда во входной последовательности в алфавите

1. {А, н, ю, т} встречается имя “Анюта”;

2. {А, л, е, ш} встречается имя “Алеша”;

3. {И, р, н, а} встречается имя “Ирина”;

4. {С, а, ш} встречается имя “Саша”;

5. {Д, а, я, н} встречается имя “Даяна”;

6. {Н, и, а} встречается имя “Нина”;

7. {А, н, ж, е, л} встречается имя “Анжела”;

8. {А, н, т, о} встречается имя “Антон”;

9. {С, е, р, ж, а} встречается имя “Сережа”;

10. {Л, и, я} встречается имя “Лилия”.

4.2.3. С помощью совокупности четверок и диаграммы опишите работу автомата, представляющего троичный сумматор последовательного действия.

4.2.4. Постройте конечный автомат таблично, складывающий:

Решение.

4.2.5. Постройте конечный автомат таблично, сравнивающий два числа x₁ и x₂, заданные в двоичной системе счисления. При совпадении разрядов на выходе формируется сигнал 0, иначе 1. X = {00, 01, 10, 11}, Y = {0, 1}.

Решение.

Функционирование системы определяется двумя состояниями: Q = {q₀, q₁}, где q₀ – состояние, соответствующее равенству разрядов, иначе q₁ .