Wykonanie: Krakowian Konrad 140059 Rakowski Bartosz 140116

mgr inż. A. Sterna Poniedziałek, godz. 15.15 10.04.2006r.

Sprawozdanie nr 7

ZASTOSOWANIE JĘZYKA WYRAŻEŃ NATURALNYCH DO SYNTEZY I ANALIZY AUTOMATÓW SKONCZOŃYCH

1. Cel ćwiczenia

Celem ćwiczenia jest nabycie praktycznej umiejętności projektowania i technicznej realizacji automatów przy zastosowaniu języka wyrażeń regularnych.

2. Program ćwiczenia:

1. Przeprowadzić syntezę abstrakcyjną wyrażenia regularnego (z2z2z1 + z2z1)*z1:

1,4 - są sobie równoważne

4
1 , 5
4 , 6
5

Po minimalizacji:

Tablica przejść automatu Moore'a:

WY	y0	y0	y0	y0	y0	y1	y0
WE\stany	0	1	2	3	4	5	*
z1	5	4	3	5	5	*	*
z2	1	2	*	1	1	*	*

Tablica przejść automatu Moore'a po minimalizacji:

WY	y0	y0	y0	y1	y0
WE\stany	0	1	2	3	*
z1	3	0	0	*	*
z2	1	2	*	*	*

Wprowadzamy nowe oznaczenia:

0
q₀

1
q₁

2
q₂

3
q₃

*
q₄

Ostateczna wersja tablicy przejść automatu Moore'a:

WY	y0	y0	y0	y1	y0
WE\stany	q0	q1	q2	q3	q4
z1	q3	q0	q0	q4	q4
z2	q1	q2	q4	q4	q4

Graf automatu Moore'a narysowany na podstawie powyższej tablicy:

y₀

z₁ z₂

z₂

y₀ z₁ y₀

z₁ z₂

y₁ z₁,z₂ y₀

z₁,z₂

2. Przeprowadzić syntezę strukturalną na podstawie grafu automatu Moore'a wyznaczonego w poprzednim punkcie:

Kodowanie sygnałów:

z1	0
z2	1
y0	0
y1	1

	Q1	Q2	Q3	Y
q0	0	0	0	0
q1	0	0	1	0
q2	0	1	0	0
q3	0	1	1	1
q4	1	0	0	0

Q2 Q3
Q1	00	01	11	10
0	0	0	1	0
1	0	-	-	-

Y = Q_2*Q₃

Zakodowana tablica automatu:

		Q1	Q2	Q3	Q1	Q2	Q3
z1	0	0	0	0	0	1	1
		0	0	0	1	0	0	0
		0	0	1	0	0	0	0
		0	0	1	1	1	0	0
		0	1	0	0	1	0	0
	z2	1	0	0	0	0	0	1
		1	0	0	1	0	1	0
		1	0	1	0	1	0	0
		1	0	1	1	1	0	0
		1	1	0	0	1	0	0

Minimalizacja siatkami Karnaugh'a:

Q2Q3
zQ1	00	01	11	10
00	0	0	1	0
01	-	-	-	-
11	-	-	-	-
10	0	0	1	1
Q2Q3
zQ1	00	01	11	10
00	-	-	-	-
01	0	-	-	-
11	0	-	-	-
10	-	-	-	-

J = z_*Q₂ + Q_2*Q₃ K = 0

Q2Q3
zQ1	00	01	11	10
00	1	0	-	-
01	0	-	-	-
11	0	-	-	-
10	0	1	-	-
Q2Q3
zQ1	00	01	11	10
00	-	-	1	1
01	-	-	-	-
11	-	-	-	-
10	-	-	-	1

J = z'_*Q₁'_*Q₃' + z_*Q₃ K = 1

Q2Q3
zQ1	00	01	11	10
00	1	-	-	0
01	0	-	-	-
11	0	-	-	-
10	1	-	-	0
Q2Q3
zQ1	00	01	11	10
00	-	1	1	-
01	-	-	-	-
11	-	-	-	-
10	-	1	1	-

J = Q₁'_*Q₂' K = 1

Schemat układu:

3. Uwagi i wnioski:

Synteza abstrakcyjna wyrażenia regularnego sprawiła nam początkowo trudność. Wynikało to z tego, że reguła „Indeks miejsca końcowego wyrażenia regularnego umieszcza się we wszystkich tych miejscach przed podstawowych, w których jest umieszczony indeks miejsca początkowego” w przypadku naszego wyrażenia nie może zostać użyta. Najlepszym sposobem sprawdzenia poprawności było najpierw narysowanie grafu bezpośrednio na podstawie wyrażenia a następnie przeprowadzenie syntezy i sprawdzenie czy grafy się pokrywają. Kolejnym zadaniem było przeprowadzenie syntezy strukturalnej. Nie sprawiło nam to już żadnych problemów, ponieważ podobną syntezę przeprowadziliśmy już na poprzednim ćwiczeniu. Ostatecznie zmontowany układ działał poprawnie.

1

q₄

q₃

q₂

q₁

q₀

---