Практическое занятие №10. Задачи синтеза автоматов

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

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

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

Решение.

q₀0® q₀0 q₀1® q₁1

q₁0® q₀0 q₁1® q₂1

q₂0® q₀0 q₂1® q₃1

q₃0® q₀0 q₃1® q₀*

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

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

Символы алфавита	Состояния
x₁	x₂	q₀	q₁
		q₀,0	q₀,1
		q₀,1	q₁,0
		q₀,1	q₁,0
		q₁,0	q₁,1

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

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){Л, и, я} встречается имя “Лилия”.

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

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

0)четные натуральные числа в D₅;	1)нечетные натуральные числа в D₈;
2)натуральные числа в D₄;	3)нечетные натуральные числа в D₆;
4)четные натуральные числа в D₆;	5)нечетные натуральные числа в D₅;
6)четные натуральные числа в D₇;	7)натуральные числа в D₃;
8)четные натуральные числа в D₈;	9)нечетные натуральные числа в D₇

Решение.

Символы алфавита	Состояния
x₁	x₂	q₀	q₁

Практическое занятие №11. Логика предикатов.

Предикатом арности n (n-арным, или n-местным предикатом) называют функцию от n переменных Q(x₁, x₂, … ,x_n), определенную на декартовом произведении множеств: X₁´X₂´ …´X_n и принимающую значения из множества {И, Л}.

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

1. Постройте матрицу одноместного предиката Р(x), если:

P(x) = "x кратно 2", где xÎ [1, 14)

x

P(x) Л И Л И Л И Л И Л И Л И Л

2. Изобразите геометрически множество истинности двуместного предиката P(x,y) = 1/4x ³ 1/4y”, если x, y Î (-2, 5];

Построим график прямой: 1/4y =1/4x; y = x;

x y

Проверим точку выше графика прямой y = x,

например, с координатами (-1; 2).

Подставим координаты в неравенство:

1/4 (-1) ³ 1/4(2) – это ложно, поэтому
Y 0 X -2 5 -2

область истинности предиката расположена ниже прямой, включая ее точки (т.к. нестрогое неравенство).

⇐ Предыдущая 2 3 4 5 6 789 10 11 Следующая ⇒