Zadanie 1
Dany jest automat o tablicy przejść-wyjść. Wyznaczyć automat względem niego minimalny.
x1x2
S
00
01
11
10
1 3/0 1/- -/- -/-
2 6/- 2/0 1/- -/-
3 -/1 -/- 4/0 -/-
4
1/0 -/- -/- 5/1
5 -/- 5/- 2/1 1/1
6 -/- 2/1 6/- 4/1
Zadanie 2
Zminimalizować automat o zadanej tablicy przejść-wyjść.
X
S X1
X2
X3
1 3/0 -/- 2/-
2 -/- 4/0 6/0
3 5/1 -/- -/0
4 -/- 1/1 1/-
5 1/- -/- 6/-
6 4/- 5/- 6/-
Zadanie 3
Zminimalizować automat zadany następującą tablicą przejść-wyjść.
X
S
0 1
1 3/- -/-
2 -/- 6/0
3 4/1 5/-
4 6/1 -/-
5 5/- 1/-
6 4/1 7/1
7 2/0 3/0
Zminimalizować automat zadany następującą tablicą przejść-wyjść.
X
S 0
1
1 8/0 7/1
2 3/0 5/0
3 2/0 1/0
4 5/1 8/0
5 8/0 4/1
6 5/1 3/0
7 1/1 8/0
8 4/0 6/1
Zadanie 5
Zminimalizować automat zadany następującą tablicą przejść-wyjść.
X
S
X1
X2
X3
1
2/0 -/- 6/0
2 4/0 5/1 7/0
3 6/0 8/1 2/0
4
3/0 -/- 8/0
5 -/- 4/1 -/0
6
3/0 2/- 4/0
7 5/1 4/1 -/-
8 -/- 6/1 5/0
Zadanie 6
Zminimalizować automat zadany następującą tablicą przejść-wyjść.
X
S X1
X2
X3
X4
1 -/- 5/1 1/- 3/1
2 -/- 2/- 5/1 6/1
3
6/0 -/- -/- 2/1
4 -/1 -/- 3/0 -/-
5 1/- 5/0 6/- -/-
6 4/- 6/- -/- -/-
Zminimalizować automat zadany następującą tablicą przejść-wyjść.
X
S 0
1
1 5/- 4/1
2 3/- 3/1
3 7/- 9/-
4 3/1 3/1
5 3/- 3/2
6 2/2 5/-
7 8/2 6/-
8 5/1 5/-
9 -/- 6/-
Zadanie 8
Następujące pary są zgodne: (v1, v2), (v1, v3), (v1, v5), (v2, v3), (v2, v5), (v3, v4), (v3, v5), (v3, v7), (v4, v6), (v4, v7), (v5, v6), (v5, v7). Obliczyć maksymalne klasy zgodności MKZ dwiema metodami:
a) algorytmem wyznaczania klas zgodnych wg par niezgodności; b) algorytmem korzystającym z par zgodnych.
Zadanie 9
Przeprowadzić minimalizację liczby stanów następujących automatów.
a)
b)
S a
b a b
S 1
2 1 2
0
2 5 0 -
1
2 - - -
1
3 5 - 0
2
1 4 - 1
2 - 1 1 1
3
4 - - -
3 1
-
1
1
4
3 6 - 2
4
2 5 1 0
5
6 - - -
5 1
-
2
1
6
5 2 - 3
c)
d)
S 0
1 0 1
S a
b c a b c
1 3
-
0
-
1
2 5 1 0 0 0
2
4 3 0 0
2
3 - 2 0 - 0
3
- 5 - 1
3
4 - 3 0 - 1
4
6 6 - 0
4
1 - 4 0 - 1
5
6 6 0 -
5
6 - - 0 - -
6
- - - -
6
5 1 - 0 1 -
f)
S 1
2 1 2
S 1
2 1 2
1
3 2 1 1
1
1 4 0 1
2
3 2 0 1
2
4 3 1 0
3
2 3 0 1
3
5 2 1 0
4
3 4 1 1
4
1 3 0 0
5
1 2 0 0
Zadanie 10
Wyznaczyć automaty minimalne dla następujących tablic przejść-wyjść.
a)
b)
S a
b a b
S a
b c a b c
0
2 5 0 -
1
1 2 5 0 - 0
1
3 5 - 0
2
2 3 4 0 - 0
2 - 1 1 1
3
2 1 4 0 - 0
3 1
-
1
1
4
- 2 7 - - 1
4
2 5 1 0
5
- 1 7 - - 1
5 1
-
2
1
6
1 2 5 - - 0
6 1
-
2
1
7
1 2 8 1 1 0
7
5 8 - 1
8
6 3 6 0 0 1
8
6 7 - 1
c)
S a
b c d y
1 1 5 - 9 0
2
3 2 6 - 0
3 3 2 - 9 0
4 4 10 - - 0
5
1 5 6 - 0
6 - 10 6 8 1
7 - 10 7 8 1
8 4 - 7 8 1
9 1 - 6 9 0
10 3 10 7 - 0
Zadanie 11
Dla automatów z zadania 10 wyznaczyć rodziny wszystkich maksymalnych zbiorów stanów sprzecznych.
Dla podanych poniżej automatów przeprowadzić minimalizację liczby stanów metodą łączenia wierszy.
a)
b)
S 0
1 0 1
S 0
1 0 1
1
2 3 0 0
1
- 3 1 0
2
1 3 0 0
2
- 4 1 0
3
4 5 1 1
3
3 1 1 1
4
3 5 1 1
4
4 2 1 1
5
1 3 1 0
5
5 4 1 0
Zadanie 12
Zminimalizować i zrealizować na przerzutnikach typu D oraz JK automaty podane w tablicach poniżej.
a)
b)
S a
b c d a b c d
S 0
1 0 1
1 - 3 4 2 - 1 1 1
1
2 6 0 0
2
4 - - - 0 - - -
2
3 1 1 1
3
6 6 - - 0 1 - -
3
- 4 - 0
4 - 6 1 5 - 0 0 1
4
- 5 - 0
5
- - 2 - - - 1 -
5
3 - 1 -
6 3 - 2 3 0 - 0 1
6
7 - 1 -
7
- 8 - 0
8
- - - 1