Data wykonania ćwiczenia: 16.01.2015r.
Prowadzący: dr inż. Tomasz Kapłon
LOGIKA UKA
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
Dokonać syntezy strukturalnej
Dokonano syntezy, połączono  układ nie
automatu w oparciu o poniższe
1. działał prawidłowo, chociaż w projekcie nie
wyrażenia regularne:
było żadnego błędu  w symulatorze działa
S1 = (z1z2 + z1z1z2)* z1z2 | y1
S2 = /S1 | y2
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).
1
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
2
miejsc zapisane są takie same litery, to miejsca  podstawowe położone na prawo od tych
liter są sobie równoważne.
1 a" 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 S1
przypisujemy jedynie stanowi końcowemu (6). Korzystając z wyrażenia S2, pozostałym
stanom przypisujemy wyjście y2.
Wyjście Stan Słowo wejściowe Następny stan
z1 1
y2 0
z2 5
z1 3
y2 1
z2 2
z1 1
y2 2
z2 5
z1 *
y2 3
z2 4
z1 1
y2 4
z2 5
z1 6
y2 5
z2 *
z1 1
y1 6
z2 5
Tabela 2  tabela przejść - wyjść
3
4. Minimalizujemy tabelę  równoważne są stany, które mają takie same przejścia i wyjścia,
czyli 0a"2a"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 -> q0
1 -> q1
2 -> q2
3 -> q3
4 -> q4
5 -> q5
Y Q(t) Z Q(t+1)
z1 q1
y2 q0
z2 q3
z1 q2
y2 q1
z2 q0
z1 q5
y2 q2
z2 q0
z1 q4
y2 q3
z2 q5
z1 q1
y1 q4
z2 q3
z1 q5
y2 q5
z2 q5
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 S1
4
6. Synteza strukturalna automatu
·ð kodowanie stanów, wejść i wyjść
qi Q2 Q1 Q0
q0 0 0 0
q1 0 0 1
q2 0 1 0
q3 0 1 1
q4 1 0 0
q5 1 0 1
Tabela 4  kodowanie stanów
zi Z
z1 0
z2 1
Tabela 5  kodowanie sygnałów wejściowych
yi Y
y1 0
y2 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 t+1
Q2Q1Q0 Z Q2Q1Q0 J2 K2 J1 K1 J0 K0
0 001 0 * 0 * 1 *
000
1 011 0 * 1 * 1 *
0 010 0 * 1 * * 1
001
1 000 0 * 0 * * 1
0 101 1 * * 1 1 *
010
1 000 0 * * 1 0 *
0 100 1 * * 1 * 1
011
1 101 1 * * 1 * 0
0 001 * 1 0 * 1 *
100
1 011 * 1 1 * 1 *
0 101 * 0 0 * * 0
101
1 101 * 0 0 * * 0
Tabela 8  kodowanie tabeli przejść
5
·ð synteza wyjść
Y
Q2/ Q1Q0 00 01 11 10
0 1 1 1 1
1
0 1 1 1
Y = /Q2 + Q1 + Q0
Tabela 9  minimalizacja funkcji wyjściowej
·ð synteza wejść
J2
Q2Q1/ Q0Z 00 01 11 10
0
00
0 0 0
01 1 0 1 1
11 * * * *
10
* * * *
J2 = Q1(Q0 + /Z)
Tabela 10  synteza wejścia J przerzutnika Q2
K2
Q2Q1/ Q0Z 00 01 11 10
*
00 * * *
01 * * * *
11 * * * *
10 1 1 0 0
K2 = /Q0
Tabela 11 - synteza wejścia K przerzutnika Q2
6
J1
Q2Q1/ Q0Z 00 01 11 10
1 1
00 0 0
01 * * * *
11 * * * *
10 0 1 0 0
J1 = /Q0Z + /Q2Q0/Z
Tabela 12 - synteza wejścia J przerzutnika Q1
K1
Q2Q1/ Q0Z 00 01 11 10
*
00 * * *
01 1 1 1 1
11 * * * *
10 * * * *
K1 = 1
Tabela 13 - synteza wejścia K przerzutnika Q1
J0
Q2Q1/ Q0Z 00 01 11 10
00 1 1 * *
0
01 1 * *
11 * * * *
10 1 1 * *
J0 = /Q1 + /Z
Tabela 14 - synteza wejścia J przerzutnika Q0
7
K0
Q2Q1/ Q0Z 00 01 11 10
*
00 * 1 1
01 * * 0 1
*
11 * * *
10 * * 0 0
K0 = /Q2(/Q1 + /Z)
Tabela 15 - synteza wejścia K przerzutnika Q0
·ð 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.
8
Rysunek 5  stan q0 automatu
t t+1
Y
Q Z Q
q0 z1 q1 y2
Tabela 16
Rysunek 6
9
t t+1
Y
Q Z Q
q1 z1 q2 y2
Tabela 17
Rysunek 7
t t+1
Y
Q Z Q
q2 z2 q0 y2
Tabela 18
Rysunek 8
10
t t+1
Y
Q Z Q
q0 z2 q3 y2
Tabela 19
Rysunek 9
t t+1
Y
Q Z Q
q3 z1 q4 y1
Tabela 20
Rysunek 10
Na tym etapie automat zaakceptował podane przez nas wyrażenie regularne w postaci z1z1z2z2z1
 na wyjściu pojawiło się y1 (rys. 10).
11
t t+1
Y
Q Z Q
q4 z2 q3 y2
Tabela 21
Rysunek 11
t t+1
Y
Q Z Q
q3 z2 q5 y2
Tabela 22
Rysunek 12
12
W tym kroku podaliśmy na stan q3 słowo z2  takie przejście nie było określone w wyrażeniu
regularnym, więc automat przeszedł w dodatkowy stan q5 (rys. 12), który wprowadziliśmy do
tego celu.
13


Wyszukiwarka

Podobne podstrony:
OI Wyrazenia regularne latex
Wyrazenia regularne Leksykon kieszonkowy Wydanie II wyrlk2
Wyrazenia regularne Leksykon kieszonkowy Wydanie II wyrlk2
Wyrazenia regularne Wprowadzenie wyrawp
Wyrażenia regularne Leksykon kieszonkowy
logika 205
Układ Regulacji Kaskadowej 2
Uk? regulacji automatycznej
regulamin labmp ogarnijtemat com
baska regulamin

więcej podobnych podstron