Data wykonania ćwiczenia: 05.12.2014r.
Prowadzący: dr inż. Tomasz Kapłon
LOGIKA UKA
ADÓW CYFROWYCH
Temat: Komputerowa analiza automatów skończonych.
I. Cel ćwiczenia
Zapoznanie się z testowaniem i identyfikacją automatów za pomocą programu LABLUC.
II. Program ćwiczenia
Wykonanie
L.p. Zadanie
Testować w programie i na podstawie testów narysować graf przejść
Wykonano
1.
automatu aut4
Testować w programie i na podstawie testów narysować graf przejść
Wykonano
2.
automatu aut12
Testować w programie i na podstawie testów narysować graf przejść
Wykonano
3.
automatu aut7
Tabela 1
III. Wstęp teoretyczny
Analizę automatu skończonego należy przeprowadzić, gdy chcemy określić działanie
automatu, którego grafu przejść nie znamy, ale znamy zbiory sygnałów wejściowych i
wejściowych. Podstawowym problemem tego ćwiczenia jest określenie stanu automatu 
pojawienie się dwa razy tego samego sygnału wyjściowego nie oznacza, że automat jest w tym
samym stanie. Aby zidentyfikować stany, należy podawać odpowiednie sekwencje sygnałów
wejściowych, które pomogą nam określić, w którym stanie automat obecnie się znajduje. Zanim
narysujemy gotowy graf przejść, należy podczas testowania na bieżąco rysować graf o strukturze
drzewiastej (graf z pętlami), który pomoże nam w określeniu grafu przejść.
IV. Realizacja ćwiczenia
W celu uruchomienia programu LABLUC należy uruchomić DOSBOX i wpisać następujące
komendy:
mount c c:/LABLUC //zamontowanie katalogu jako partycji c (c:/LABLUC to przykładowa ścieżka
dostępu do folderu z programem
c: //przejście do katalogu
automat //uruchomienie programu
Następnie należy przejść do opcji  Analiza i  Wybór automatu i wpisać nazwę pliku z
automatem do testowania.
Testowaliśmy trzy różne automaty. W pierwszym punkcie pokazano krok po kroku testowanie
automatu, w następnych punktach tylko gotowe drzewa i grafy.
1. Aut4
Automat ten ma określony zbiór Z = {z1,z2,z3}  przy próbie nadania sygnału z0 lub z4 otrzymujemy
komunikat  Przejście nieokreślone! .
a) rozpoczynamy testowanie sekwencją wejść z1,z1,z1
Rysunek 1 Rysunek 2
Zauważmy, że stan q1 i q2 mogą być tożsame  aby to sprawdzić, podaliśmy z2 na q1 i
otrzymaliśmy wyjście y1, natomiast po podaniu z2 na q2 otrzymaliśmy sygnał y2  stąd
wniosek, że stany q1 i q2 są różne (rys. 1). Teraz rozważmy, jaki stan otrzymujemy po podaniu
sygnałów z1,z1,z1. Może on być równy stanowi q1 lub q2, może też być zupełnie innym stanem.
Aby go zidentyfikować, wyzerowaliśmy automat i podaliśmy z1,z1,z1,z2 (rys. 2).
Można zauważyć, że podanie na badany stan q sygnału z2 (linia przerywana) ma taki sam
wynik, jak podanie z2 na stan q1. Zatem q = q1. Zaznaczyliśmy to pętlą na rys. 3.
b) Następnie rozważamy tożsamość stanu q2 i q oznaczonych na rys. 3 znakiem zapytania.
Wyzerowawszy automat, podajemy sekwencję z1,z2,z2 (rys. 4). Otrzymujemy wyjścia y2,y1,y1,y2
 określamy zatem stan q jako q2 (pętla na rys.5).
Rysunek 3 Rysunek 4
c) W kolejnym kroku próbujemy określić, czy stan q, do którego przyporządkowany jest sygnał
wyjściowy y2 jest równy stanowi początkowemu q0. Zerujemy automat, po czym podajemy
sekwencję z1,z1,z2,z2. Otrzymaliśmy na wyjściu y3. Teraz zerujemy i podajemy na stan
początkowy sygnał z3. Również otrzymaliśmy sygnał wyjściowy y3 (rys. 5). Na podstawie tej
obserwacji zapisujemy, że stan q = q0 i rysujemy powracającą pętlę (rys. 6).
Rysunek 5 Rysunek 6
d) Na stan początkowy podajemy kombinację wejść z2,z1. Otrzymujemy wyjście y2, więc automat
może być w stanie q0 (rys. 7). Aby sprawdzić tą hipotezę, na nieokreślony na razie stan q
podajemy z1,z1 (rys. 8  linie przerywane) i obserwujemy, że otrzymane wyjścia odpowiadają
podaniu na stan q0 takiej sekwencji.
Rysunek 7 Rysunek 8
e) Zerujemy automat. Zadajemy wejścia z2,z2. Rozważamy, do którego stanu przypisane jest
otrzymane wyjście y1 (rys. 9). Po podaniu na badany stan kombinacji z1,z2 określamy że jest to
stan q1.
Rysunek 9
f) Testujemy podanie stanu z3 na początek automatu. Otrzymujemy wyjście y2, a po
sprawdzeniu kombinacji z3,z1 podanej na q0, utożsamiamy badany stan z q0 (rys. 10).
Następnie sprawdzamy podanie sygnału z3 na stan q1  zerujemy automat i wprowadzamy
z1,z3. Otrzymujemy wyjście y1, a na badany stan podajemy z1,z2  identyfikujemy go jako q1
(rys. 10).
Rysunek 10
g) Pozostało nam jeszcze zadanie sygnału z3 na stan q2 i q3. Najpierw podajemy na q0 sekwencję
z1,z1,z3. Otrzymany stan z wyjściem y1 sprawdzamy sygnałem z2 i oznaczamy jako q2.
Aby określić przejście automatu ze stanu q3 za pomocą sygnału z3, podajemy na q0 z2,z3 i
otrzymujemy nie występujące wcześniej wyjście y0. Przypisujemy je do nowego stanu q4,
który testujemy kolejno sygnałami z1, z2 i z3 (rys. 11).
Rysunek 11
h) Rys. 12 przedstawia gotowe drzewo d4. Można je uzupełnić o reprezentujące je wyrażenie
symboliczne d4++ oraz o tabelę przyporządkowującą wyjścia do stanów.
Rysunek 12
d4++ =
0
(y21(z1y12(z1y13(z1y1,z2y24(z1y15(z1y16(z1y17(z2y1)7)6)5,z2y3)4,z3y14(z2y2)4),z2y13(z2y2)3,z3y13(z1y14(z2y25(z1y1
6
(z2y1)6)5)4)3)2,z3y22(z3y23(z1y1)3)2,z2y32(z1y23(z1y14(z1y15(z2y2)6(z2y3)6)5)4)3,z2y13(z1y14(z2y2)4)3,z3y03(z1y04(
z2y0(5(z3y1)5)4)3)2)1)0
Q Y
q0 y2
q1 y1
q2 y1
q3 y3
q4 y0
Tabela 2
i) Na podstawie drzewa d4 narysowano graf G4 (rys. 14) i zapisano charakteryzujące go
wyrażenie symboliczne G4++.
Rysunek 13
G4++ = 0(q01(z1q12(z3q1,z2q23(z3,q2,z1q1,z2q0)3,z1q2)2,z3q0,z2q32(z3q43(z1q4,z2q4,z3q1)3,z2q1,z1q0)2)1)0
2. Aut12
Z = {z1,z2}
a) Drzewo d12, wyrażenie symboliczne d12++ i tabela przyporządkowująca wyjścia do stanów
Rysunek 14
d12++ = 0(y11(z1y12(z1y33(z1y14(z2y3(5z2y3)5)4)3)2,z2y22(z1y23(z2y1(4z2y15(z1y16(z2y2)6)5)4)3)2)1)0
Q Y
q0 y1
q1 y1
q2 y3
q3 y2
q4 y1
Tabela 3
b) Graf G12 i wyrażenie G12++
Rysunek 15
G12++ = 0(q01(z1q12(z1q23(z2q2,z1q44(z1q4,z2q2)4)3,z2q4)2, z2q32(z1q3,z2q1)2)1)0
3. Aut7
Z = {z1,z2,z3}
a) Drzewo d7, wyrażenie symboliczne d7++ i tabela przyporządkowująca wyjścia do stanów
Rysunek 16
d7++ =
0
(y11(z1y12(z1y13(z3y14(z2y15(z1y16(z1y17(z3y18(z2y29(z3y210(z1y111(z1y112(z2y213(z2y314(z1y215(z2y316(z2y117(z2y118(
z2y219(z2y320(z3y0 21(z1y022(z2y023(z3y1)23)22)21)20)19)18)17)16)15)14)13)12)11)10)9)8)7)6)5)4)3)2)1)0
Q Y
q0 y0
q1 y1
q2 y1
q3 y2
q4 y1
q5 y0
Tabela 4
b) Graf G7 i wyrażenie G7++
Rysunek 17
G7++ = 0(q01(z2q0,z1q12(z3q1,z1q23(z3q2, z1q1, z2q1)3,z2q33(z3q3,z1q2z2q44(z1q3,z2q2,z3q55(z3q2,z1q5,z2q5)5,
z3q5)4)3)2)1)0