Главная / Алгоритмы и дискретные структуры / Введение в теорию автоматов / Тест 1

Введение в теорию автоматов - тест 1

Упражнение 1:

Номер 1

Автомат задан в табличной форме. Представить его в виде графа.

w1 w2 w3 w4
 a1 a2 a3 a4
z1 a2 a2 - a1
z2 - a3 a4 -
z3 a4 a1 a2 a2

	w1	w2	w3	w4
	a1	a2	a3	a4
z1	a2	a2	-	a1
z2	-	a3	a4	-
z3	a4	a1	a2	a2

Ответ:

(1)

(2)

(3) нет правильного графа

Номер 2

Автомат задан в табличной форме. Представить его в виде графа.
w1 w2 w3 w1
 a1 a2 a3 a4
z1 a2 a2 - a1
z2 - a3 a4 -
z3 a4 a1 a2 a2

	w1	w2	w3	w1
	a1	a2	a3	a4
z1	a2	a2	-	a1
z2	-	a3	a4	-
z3	a4	a1	a2	a2

Ответ:

(1)

(2)

(3) нет правильного графа

Номер 3

Автомат задан в табличной форме. Представить его в виде графа.   
w1 w3 w2 w1
 a1 a2 a3 a4
z1 a2 - - a1
z2 - a3 a4 -
z3 a4 a1 a2 a2

	w1	w3	w2	w1
	a1	a2	a3	a4
z1	a2	-	-	a1
z2	-	a3	a4	-
z3	a4	a1	a2	a2

Ответ:

(1)

(2)

(3) нет правильного графа

Упражнение 2:

Номер 1

 Для автомата Мили заданы таблицы переходов (табл.1) и выходов (табл.2).  Построить граф автомата и его матричную форму задания.
a1 a2 a3
z1 a2 a1 a1
z2 a3 a3 a2
a1 a2 a3
z1 w1 w3 w1
z2 w2 w2 w2

	a1	a2	a3
z1	a2	a1	a1
z2	a3	a3	a2

	a1	a2	a3
z1	w1	w3	w1
z2	w2	w2	w2

Ответ:

(1)

-	z1/w1	z2/w2
z1/w3	-	z2/w2
z1/w1	Z2/w2	-

(2)

-	z1/w1	z2/w2
z1/w3	-	z2/w2
z1/w1	Z2/w2	-

(3)

-	z1/w3	z1/w1
z1/w1	-	z2/w2
z2/w2	z2/w2	-

Номер 2

Для автомата Мили заданы таблицы переходов (табл.1) и выходов(табл.2). Построить граф автомата и его матричную форму задания.
a1 a2 a3
z1 a2 a1 a1
z2 a3 a3 a2
a1 a2 a3
z1 w3 w1 w4
z2 w2 w3 w2

	a1	a2	a3
z1	a2	a1	a1
z2	a3	a3	a2

	a1	a2	a3
z1	w3	w1	w4
z2	w2	w3	w2

Ответ:

(1)

-	z1/w3	z2/w2
z1/w1	-	z2/w3
z1/w4	Z2/w2	-

(2)

-	z1/w3	z2/w2
z1/w1	-	z2/w3
z1/w4	Z2/w2	-

(3)

-	z1/w3	z1/w1
z1/w1	-	z2/w2
z2/w2	Z2/w2	-

Номер 3

Для автомата Мили заданы таблицы переходов (табл.1) и выходов(табл.2). Построить граф автомата и его матричную форму задания.
a1 a2 a3
 z1 a2 a1 a1
z2 a3 a3 a2
a1 a2 a3
 z1 w1 w3 w1
z2 w2 w2 w2

	a1	a2	a3
z1	a2	a1	a1
z2	a3	a3	a2

	a1	a2	a3
z1	w1	w3	w1
z2	w2	w2	w2

Ответ:

(1)

-	z1	z2
z1	-	z2
z1	z2	-

w1
w2
w3

(2)

-	z1	z2
z1	-	z2
z1	z2	-

w1
w2
w3

(3)

-	z1/w1	z2/w2
z1/w3	-	z2/w2
z1/w1	z2/w2	-

Упражнение 4:

Номер 2

Автомат задан в матричной форме. Представитьграфическую форму задания автомата.
 $C=\left|\left|\begin{array}{cccc}
z1& -&  z2&  z3\\
-&  z2&  z1&  -\\
z2&  -&  -&  z1\\
z3& z2&  -&  - \end{array}\right|\right|,
w=\left|\left|\begin{array}{ccc}w1\\ w2 \\ w3\\ w4 \end{array}\right|\right|$

Ответ:

(1)

(2)

(3)

Номер 3

 Автомат представлен в матричной форме. Задать автомат в виде графа и в табличной форме.
 $С=\left|\left|\begin{array}{ccc}
z2/w1&  -&  z1/w1\\
z1/w1&  -&   z2/w2\\
z1/w2&  z2/w1& - \end{array}\right|\right|$

Ответ:

(1)

z\a	a1	a2	a3
z1	a3	a1	a1
z2	a1	a2	a3

z\a	a1	a2	a3
z1	w2	w1	w2
z2	w1	w2	w1

(2)

z\a	a1	a2	a3
z1	a3	a1	a1
z2	a1	a2	a3

z\a	a1	a2	a3
z1	w1	w1	w2
z2	w1	w2	w1

(3)

z\a	a1	a2	a3
z1	a3	a1	a1
z2	a1	a3	a2

z\a	a1	a2	a3
z1	w1	w1	w2
z2	w1	w1	w1

Упражнение 5:

Номер 1

На рисунке дан граф автомата Мура. Представить  его  в  теоретико-множественной  форме .

Ответ:

(1)

(2)

(3)

Номер 2

 На рисунке дан граф автомата Мура. Представить  его в теоретико-множественной  форме.

Ответ:

(1)

(2)

(3)

Номер 3

На рисунке дан граф автомата Мура. Представить  его в теоретико-множественной  форме.

Ответ:

(1)

(2)

(3)

Упражнение 6:

Номер 1

Автомат представлен в   теоретико-множественной  форме:   Дать его табличную форму описания.

Ответ:

(1)

\w	w1	w2	w2
z\a	a1	a2	a3
z1	-	-	a2
z2	a3	a2	a1

(2)

\w	w1	w2	w1
z\a	a1	a2	a3
z1	a1	-	a2
z2	a3	a2	a1

(3)

\w	w1	w2	w2
z\a	a1	a2	a3
z1	-	a1	a2
z2	a3	-	-

Номер 2

Автомат представлен в теоретико-множественной  форме:    Дать его табличную форму описания.

Ответ:

(1)

\w	w1	w2	w2
z\a	a1	a2	a3
z1	-	-	a2
z2	a3	a2	a1

(2)

\w	w1	w1	w2
z\a	a1	a2	a3
z1	-	a1	a2
z2	a3	a3	a1

(3)

\w	w1	w2	w2
z\a	a1	a2	a3
z1	-	a1	a2
z2	a3	-	-

Номер 3

Автомат представлен в теоретико-множественной  форме:  Дать его табличную форму описания.

Ответ:

(1)

\w	w3	w1	w2
z\a	a1	a2	a3
z1	a2	a1	a2
z2	-	a3	a1

(2)

\w	w1	w1	w2
z\a	a1	a2	a3
z1	-	a1	a2
z2	a3	a3	a1

(3)

\w	w1	w2	w3
z\a	a1	a2	a3
z1	a2	a1	a2
z2	a3	a3	-

Главная / Алгоритмы и дискретные структуры / Введение в теорию автоматов / Тест 1