Практическая работа специальности 09.02.01.

Практическое занятие № 14

Тема: «Построение простейших автоматов»

Ход работы

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

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

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

Решение.

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

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

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

0) последовательность 0000;

1) последовательность 1111;

2) последовательность 0110;

3) последовательность 0111;

4) последовательность 1000;

5) последовательность 0011;

6) последовательность 0010;

7) последовательность 1110;

8) последовательность 0001;

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

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

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

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

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

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

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

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

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

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

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

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

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

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