Data wykonania ćwiczenia: 05.12.2014r.
Prowadzący: dr inż. Tomasz Kapłon
LOGIKA UKŁ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
L.p.
Zadanie
Wykonanie
1.
Testować w programie i na podstawie testów narysować graf przejść
automatu aut4
Wykonano
2.
Testować w programie i na podstawie testów narysować graf przejść
automatu aut12
Wykonano
3.
Testować w programie i na podstawie testów narysować graf przejść
automatu aut7
Wykonano
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 = {z
1
,z
2
,z
3
} – przy próbie nadania sygnału z
0
lub z
4
otrzymujemy
komunikat „Przejście nieokreślone!”.
a) rozpoczynamy testowanie sekwencją wejść z
1
,z
1
,z
1
Rysunek 1
Rysunek 2
Zauważmy, że stan q
1
i q
2
mogą być tożsame – aby to sprawdzić, podaliśmy z
2
na q
1
i
otrzymaliśmy wyjście y
1,
natomiast po podaniu z
2
na q
2
otrzymaliśmy sygnał y
2
– stąd
wniosek, że stany q
1
i q
2
są różne (rys. 1). Teraz rozważmy, jaki stan otrzymujemy po podaniu
sygnałów z
1
,z
1
,z
1
. Może on być równy stanowi q
1
lub q
2
, może też być zupełnie innym stanem.
Aby go zidentyfikować, wyzerowaliśmy automat i podaliśmy z
1
,z
1
,z
1
,z
2
(rys. 2).
Można zauważyć, że podanie na badany stan q sygnału z
2
(linia przerywana) ma taki sam
wynik, jak podanie z
2
na stan q
1.
Zatem q = q
1
. Zaznaczyliśmy to pętlą na rys. 3.
b) Następnie rozważamy tożsamość stanu q
2
i q oznaczonych na rys. 3 znakiem zapytania.
Wyzerowawszy automat, podajemy sekwencję z
1
,z
2,
z
2
(rys. 4)
.
Otrzymujemy wyjścia y
2
,y
1
,y
1
,y
2
– określamy zatem stan q jako q
2
(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 y
2
jest równy stanowi początkowemu q
0
. Zerujemy automat, po czym podajemy
sekwencję z
1
,z
1
,z
2
,z
2
. Otrzymaliśmy na wyjściu y
3
. Teraz zerujemy i podajemy na stan
początkowy sygnał z
3
. Również otrzymaliśmy sygnał wyjściowy y
3
(rys. 5). Na podstawie tej
obserwacji zapisujemy, że stan q = q
0
i rysujemy powracającą pętlę (rys. 6).
Rysunek 5
Rysunek 6
d) Na stan początkowy podajemy kombinację wejść z
2
,z
1
. Otrzymujemy wyjście y
2
, więc automat
może być w stanie q
0
(rys. 7).
Aby sprawdzić tą hipotezę, na nieokreślony na razie stan q
podajemy z
1
,z
1
(rys. 8 – linie przerywane) i obserwujemy, że otrzymane wyjścia odpowiadają
podaniu na stan q
0
takiej sekwencji.
Rysunek 7
Rysunek 8
e) Zerujemy automat. Zadajemy wejścia z
2,
z
2
. Rozważamy, do którego stanu przypisane jest
otrzymane wyjście y
1
(rys. 9). Po podaniu na badany stan kombinacji z
1
,z
2
określamy że jest to
stan q
1
.
Rysunek 9
f) Testujemy podanie stanu z
3
na początek automatu. Otrzymujemy wyjście y
2
, a po
sprawdzeniu kombinacji z
3
,z
1
podanej na q
0
, utożsamiamy badany stan z q
0
(rys. 10).
Następnie sprawdzamy podanie sygnału z
3
na stan q
1
– zerujemy automat i wprowadzamy
z
1
,z
3
. Otrzymujemy wyjście y
1
, a na badany stan podajemy z
1
,z
2
– identyfikujemy go jako q
1
(rys. 10).
Rysunek 10
g) Pozostało nam jeszcze zadanie sygnału z
3
na stan q
2
i q
3.
Najpierw podajemy na q
0
sekwencję
z
1
,z
1
,z
3
. Otrzymany stan z wyjściem y
1
sprawdzamy sygnałem z
2
i oznaczamy jako q
2
.
Aby określić przejście automatu ze stanu q
3
za pomocą sygnału z
3
, podajemy na q
0
z
2,
z
3
i
otrzymujemy nie występujące wcześniej wyjście y
0
. Przypisujemy je do nowego stanu q
4
,
który testujemy kolejno sygnałami z
1
, z
2
i z
3
(rys. 11).
Rysunek 11
h) Rys. 12 przedstawia gotowe drzewo d
4
. Można je uzupełnić o reprezentujące je wyrażenie
symboliczne d
4
++
oraz o tabelę przyporządkowującą wyjścia do stanów.
Rysunek 12
d
4
++
=
0
(y
2
1
(z
1
y
1
2
(z
1
y
1
3
(z
1
y
1,
z
2
y
2
4
(z
1
y
1
5
(z
1
y
1
6
(z
1
y
1
7
(z
2
y
1
)
7
)
6
)
5
,z
2
y
3
)
4
,z
3
y
1
4
(z
2
y
2
)
4
),z
2
y
1
3
(z
2
y
2
)
3
,z
3
y
1
3
(z
1
y
1
4
(z
2
y
2
5
(z
1
y
1
6
(z
2
y
1
)
6
)
5
)
4
)
3
)
2
,z
3
y
2
2
(z
3
y
2
3
(z
1
y
1)
3
)
2
,z
2
y
3
2
(z
1
y
2
3
(z
1
y
1
4
(z
1
y
1
5
(z
2
y
2
)
6
(z
2
y
3
)
6
)
5
)
4
)
3
,z
2
y
1
3
(z
1
y
1
4
(z
2
y
2
)
4
)
3
,z
3
y
0
3
(z
1
y
0
4
(
z
2
y
0
(
5
(z
3
y
1
)
5
)
4
)
3
)
2
)
1
)
0
Q Y
q
0
y
2
q
1
y
1
q
2
y
1
q
3
y
3
q
4
y
0
Tabela 2
i) Na podstawie drzewa d
4
narysowano graf G
4
(rys. 14) i zapisano charakteryzujące go
wyrażenie symboliczne G
4
++
.
Rysunek 13
G
4
++
=
0
(q
0
1
(z
1
q
1
2
(z
3
q
1
,z
2
q
2
3
(z
3
,q
2
,z
1
q
1
,z
2
q
0
)
3
,
z
1
q
2
)
2
,z
3
q
0
,z
2
q
3
2
(z
3
q
4
3
(z
1
q
4
,z
2
q
4
,z
3
q
1
)
3
,z
2
q
1
,z
1
q
0
)
2
)
1
)
0
2. Aut12
Z = {z
1
,z
2
}
a) Drzewo d
12
, wyrażenie symboliczne d
12
++
i tabela przyporządkowująca wyjścia do stanów
Rysunek 14
d
12
++
=
0
(y
1
1
(z
1
y
1
2
(z
1
y
3
3
(z
1
y
1
4
(z
2
y
3
(
5
z
2
y
3
)
5
)
4
)
3
)
2
,z
2
y
2
2
(z
1
y
2
3
(z
2
y
1
(
4
z
2
y
1
5
(z
1
y
1
6
(z
2
y
2
)
6
)
5
)
4
)
3
)
2
)
1
)
0
Q Y
q
0
y
1
q
1
y
1
q
2
y
3
q
3
y
2
q
4
y
1
Tabela 3
b) Graf G
12
i wyrażenie G
12
++
Rysunek 15
G
12
++
=
0
(q
0
1
(z
1
q
1
2
(z
1
q
2
3
(z
2
q
2
,z
1
q
4
4
(z
1
q
4
,z
2
q
2
)
4
)
3
,z
2
q
4
)
2
, z
2
q
3
2
(z
1
q
3
,z
2
q
1
)
2
)
1
)
0
3. Aut7
Z = {z
1
,z
2,
z
3
}
a) Drzewo d
7
,
wyrażenie symboliczne d
7
++
i tabela przyporządkowująca wyjścia do stanów
Rysunek 16
d
7
++
=
0
(y
1
1
(z
1
y
1
2
(z
1
y
1
3
(z
3
y
1
4
(z
2
y
1
5
(z
1
y
1
6
(z
1
y
1
7
(z
3
y
1
8
(z
2
y
2
9
(z
3
y
2
10
(z
1
y
1
11
(z
1
y
1
12
(z
2
y
2
13
(z
2
y
3
14
(z
1
y
2
15
(z
2
y
3
16
(z
2
y
1
17
(z
2
y
1
18
(
z
2
y
2
19
(z
2
y
3
20
(z
3
y
0
21
(z
1
y
0
22
(z
2
y
0
23
(z
3
y
1
)
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
q
0
y
0
q
1
y
1
q
2
y
1
q
3
y
2
q
4
y
1
q
5
y
0
Tabela 4
b) Graf G
7
i wyrażenie G
7
++
Rysunek 17
G
7
++
=
0
(q
0
1
(z
2
q
0
,z
1
q
1
2
(z
3
q
1
,z
1
q
2
3
(z
3
q
2
, z
1
q
1
, z
2
q
1
)
3
,z
2
q
3
3
(z
3
q
3
,z
1
q
2
z
2
q
4
4
(z
1
q
3
,z
2
q
2
,z
3
q
5
5
(z
3
q
2
,z
1
q
5
,z
2
q
5
)
5
,
z
3
q
5
)
4
)
3
)
2
)
1
)
0