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
Cel ćwiczenia
Celem ćwiczenia jest nabycie praktycznej umiejętności projektowania i technicznej realizacji automatów przy zastosowaniu języka wyrażeń regularnych.
Program ćwiczenia:
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
q0
1
q1
2
q2
3
q3
*
q4
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:
y0
z1 z2
z2
y0 z1 y0
z1 z2
y1 z1,z2 y0
z1,z2
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 = Q2*Q3
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*Q2 + Q2*Q3 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'*Q1'*Q3' + z*Q3 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 = Q1'*Q2' K = 1
Schemat układu:
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
q4
q3
q2
q1
q0