1
Data wykonania ćwiczenia: 16.01.2015r.
Prowadzący: dr inż. Tomasz Kapłon
LOGIKA UKŁADÓW CYFROWYCH
Temat: Zastosowanie języka wyrażeń regularnych do syntezy i analizy automatów skończonych
I.
Cel ćwiczenia
Nabycie umiejętności syntezy automatu skończonego na podstawie charakteryzującego
go wyrażenia regularnego.
II.
Program ćwiczenia
L.p.
Zadanie
Wykonanie
1.
Dokonać syntezy strukturalnej
automatu w oparciu o poniższe
wyrażenia regularne:
S
1
= (z
1
z
2
+ z
1
z
1
z
2
)* z
1
z
2
| y
1
S
2
= /S
1
| y
2
Dokonano syntezy, połączono – układ nie
działał prawidłowo, chociaż w projekcie nie
było żadnego błędu – w symulatorze działa
Tabela 1
III.
Wstęp teoretyczny
a) Automat skończony akceptuje słowa należące do języka regularnego reprezentowanego
przez wyrażenia regularne, których używamy w celu oznaczenia zbiorów słów powstałych
w wyniku konkatenacji, sumy i iteracji. Wyrażenie regularne składa się z określonych słów
połączonych znakami symbolizującymi dane operacje.
b) Synteza abstrakcyjna automatu polega na znalezieniu takiego opisu formalnego
automatu, na podstawie którego można zbudować tablice przejść i wyjść automatu.
Etapy syntezy abstrakcyjnej:
algorytm słowny
przedstawienie algorytmu słownego w postaci wyrażeń regularnych
określenie grafu przejść
IV.
Realizacja ćwiczenia
1. W celu określenia stanów automatu, należy w wyrażeniu regularnym oznaczyć miejsca
podstawowe i przedpodstawowe:
miejsce przedpodstawowe (początkowe) to miejsce, na prawo od którego stoi litera
miejsce podstawowe to miejsce, na lewo od którego stoi litera, a na prawo miejsce
przedpodstawowe
a) Na początku zaznaczamy poszczególne miejsca i oznaczamy miejsca podstawowe
kolejnymi cyframi (rys. 1).
2
Rysunek 1
b) Następnie miejsca przedpodstawowe oznacza się odpowiednimi symbolami miejsc
podstawowych według poniższych reguł:
Symbol miejsca podstawowego znajdującego się przed nawiasem iteracyjnym (0)
rozmieszcza się w miejscach początkowych członów dysjunktywnych w danym
nawiasie (człony dysjunktywne – czyli połączone znakiem sumy) oraz w miejscu
przedpodstawowym za danym nawiasem
Symbol miejsca końcowego dowolnego członu dysjunktywnego zamkniętego w
nawiasy iteracyjne (2, 5) rozmieszczamy w miejscach początkowych wszystkich
członów dysjunktywnych w danym nawiasie oraz w miejscu przedpodstawowym
bezpośrednio za danym nawiasem
Symboli miejsc podstawowych, na lewo i prawo od których stoją litery (1, 3, 4, 6) nie
rozmieszcza się niegdzie więcej i przepisuje poziom niżej
Symbol miejsca końcowego wyrażenia (7) rozmieszcza się we wszystkich tych
miejscach przedpodstawowych, gdzie umieściliśmy symbol miejsca początkowego
wyrażenia (0)
Rysunek 2
2. W drugim kroku przeprowadzamy minimalizację stanów. Jeżeli kilka miejsc
przedpodstawowych oznakowane jest jednakowym zbiorem symboli i na prawo od tych
3
miejsc zapisane są takie same litery, to miejsca „podstawowe” położone na prawo od tych
liter są sobie równoważne.
1 ≡ 3 (rys. 2)
3 -> 1
4 -> 3
5 -> 4
6 -> 5
7 -> 6
Rysunek 3
3. Następnie określamy tabelę przejść automatu (tab. 2), patrząc na miejsca przedpodstawowe i
podawane na nie litery. Jeżeli przejście za pomocą danej litery nie istnieje, oznaczamy je na
razie gwiazdką. Sygnał wyjściowy, którego wystąpienie warunkowane jest przez wyrażenie S
1
przypisujemy jedynie stanowi końcowemu (6). Korzystając z wyrażenia S
2
, pozostałym
stanom przypisujemy wyjście y
2.
Wyjście
Stan
Słowo wejściowe
Następny stan
y
2
0
z
1
1
z
2
5
y
2
1
z
1
3
z
2
2
y
2
2
z
1
1
z
2
5
y
2
3
z
1
*
z
2
4
y
2
4
z
1
1
z
2
5
y
2
5
z
1
6
z
2
*
y
1
6
z
1
1
z
2
5
Tabela 2 – tabela przejść - wyjść
4
4. Minimalizujemy tabelę – równoważne są stany, które mają takie same przejścia i wyjścia,
czyli 0≡2≡4 (tab. 2).
2 -> 0
4 -> 0
3 -> 2
5 -> 3
6 -> 4
Wprowadzamy dodatkowy stan (5), do którego przechodzi automat, jeśli dane przejście
oznaczyliśmy gwiazdką. Oznaczamy stany automatu:
0 -> q
0
1 -> q
1
2 -> q
2
3 -> q
3
4 -> q
4
5 -> q
5
Y
Q(t)
Z
Q(t+1)
y
2
q
0
z
1
q
1
z
2
q
3
y
2
q
1
z
1
q
2
z
2
q
0
y
2
q
2
z
1
q
5
z
2
q
0
y
2
q
3
z
1
q
4
z
2
q
5
y
1
q
4
z
1
q
1
z
2
q
3
y
2
q
5
z
1
q
5
z
2
q
5
Tabela 3 – zminimalizowana tabela przejść - wyjść
5. Na podstawie tabeli przejść utworzyliśmy graf automatu Moore’a (rys. 4).
Rysunek 4 – graf automatu Moore’a reprezentowanego przez wyrażenie S
1
5
6. Synteza strukturalna automatu
kodowanie stanów, wejść i wyjść
q
i
Q
2
Q
1
Q
0
q
0
0
0
0
q
1
0
0
1
q
2
0
1
0
q
3
0
1
1
q
4
1
0
0
q
5
1
0
1
Tabela 4 – kodowanie stanów
z
i
Z
z
1
0
z
2
1
Tabela 5 – kodowanie sygnałów wejściowych
y
i
Y
y
1
0
y
2
1
Tabela 6 – kodowanie sygnałów wyjściowych
kodowanie tabeli przejść
Q (t)
Q (t+1)
J
K
0
0
0
*
0
1
1
*
1
0
*
1
1
1
*
0
Tabela 7 – tabela wzbudzeń przerzutnika JK
t
t+1
t
Q
2
Q
1
Q
0
Z
Q
2
Q
1
Q
0
J
2
K
2
J
1
K
1
J
0
K
0
000
0
001
0
*
0
*
1
*
1
011
0
*
1
*
1
*
001
0
010
0
*
1
*
*
1
1
000
0
*
0
*
*
1
010
0
101
1
*
*
1
1
*
1
000
0
*
*
1
0
*
011
0
100
1
*
*
1
*
1
1
101
1
*
*
1
*
0
100
0
001
*
1
0
*
1
*
1
011
*
1
1
*
1
*
101
0
101
*
0
0
*
*
0
1
101
*
0
0
*
*
0
Tabela 8 – kodowanie tabeli przejść
6
synteza wyjść
Y
Q
2
/ Q
1
Q
0
00
01
11
10
0
1
1
1
1
1
0
1
1
1
Y = /Q
2
+ Q
1
+ Q
0
Tabela 9 – minimalizacja funkcji wyjściowej
synteza wejść
Tabela 10 – synteza wejścia J przerzutnika Q
2
K
2
Q
2
Q
1
/ Q
0
Z
00
01
11
10
00
*
*
*
*
01
*
*
*
*
11
*
*
*
*
10
1
1
0
0
K
2
= /Q
0
Tabela 11 - synteza wejścia K przerzutnika Q
2
J
2
Q
2
Q
1
/ Q
0
Z
00
01
11
10
00
0
0
0
0
01
1
0
1
1
11
*
*
*
*
10
*
*
*
*
J
2
= Q
1
(Q
0
+ /Z)
7
J
1
Q
2
Q
1
/ Q
0
Z
00
01
11
10
00
0
1
0
1
01
*
*
*
*
11
*
*
*
*
10
0
1
0
0
J
1
= /Q
0
Z + /Q
2
Q
0
/Z
Tabela 12 - synteza wejścia J przerzutnika Q
1
K
1
Q
2
Q
1
/ Q
0
Z
00
01
11
10
00
*
*
*
*
01
1
1
1
1
11
*
*
*
*
10
*
*
*
*
K
1
= 1
Tabela 13 - synteza wejścia K przerzutnika Q
1
J
0
Q
2
Q
1
/ Q
0
Z
00
01
11
10
00
1
1
*
*
01
1
0
*
*
11
*
*
*
*
10
1
1
*
*
J
0
= /Q
1
+ /Z
Tabela 14 - synteza wejścia J przerzutnika Q
0
8
K
0
Q
2
Q
1
/ Q
0
Z
00
01
11
10
00
*
*
1
1
01
*
*
0
1
11
*
*
*
*
10
*
*
0
0
K
0
= /Q
2
(/Q
1
+ /Z)
Tabela 15 - synteza wejścia K przerzutnika Q
0
schemat układu
7. Symulacja działania
Symulacja działania układu w programie Cedar Logic Simulator. Tabele nad każdym etapem
symulacji przedstawiają dane przejście. Przetestowano tylko niektóre kombinacje sygnałów
wejściowych.
9
Rysunek 5 – stan q
0
automatu
t
t+1
Q
Z
Q
Y
q
0
z
1
q
1
y
2
Tabela 16
Rysunek 6
10
t
t+1
Q
Z
Q
Y
q
1
z
1
q
2
y
2
Tabela 17
Rysunek 7
t
t+1
Q
Z
Q
Y
q
2
z
2
q
0
y
2
Tabela 18
Rysunek 8
11
t
t+1
Q
Z
Q
Y
q
0
z
2
q
3
y
2
Tabela 19
Rysunek 9
t
t+1
Q
Z
Q
Y
q
3
z
1
q
4
y
1
Tabela 20
Rysunek 10
Na tym etapie automat zaakceptował podane przez nas wyrażenie regularne w postaci z
1
z
1
z
2
z
2
z
1
– na wyjściu pojawiło się y
1
(rys. 10).
12
t
t+1
Q
Z
Q
Y
q
4
z
2
q
3
y
2
Tabela 21
Rysunek 11
t
t+1
Q
Z
Q
Y
q
3
z
2
q
5
y
2
Tabela 22
Rysunek 12
13
W tym kroku podaliśmy na stan q
3
słowo z
2
– takie przejście nie było określone w wyrażeniu
regularnym, więc automat przeszedł w dodatkowy stan q
5
(rys. 12), który wprowadziliśmy do
tego celu.