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