LUC-spr5.pdf
(
153 KB
)
Pobierz
665003217 UNPDF
Marek Karpiński (181172), Michał Kaczara(181132)
L.U.C. laboratorium – piątek 7:30 / mgr A. Sterna
SPRAWOZDANIE NR 5
TEMATY: KOMPUTEROWA REALIZACJA AUTOMATÓW SKOŃCZONYCH
1. Automat wykrywający ciągi o parzystej liczbie jedynek i nieparzystej liczbie zer
Alfabet wyjść: Y = {y0 – ciąg nie spełnia warunku, y1 – ciąg spełnia warunek}
Alfabet wewnętrzny: Q = {q0, q1, q2, q3}
Tabela przejść
Tabela wyjść
Z
Q
z0 z1
Q Y
q0 q3 q1
q0 y0
q1 q2 q0
q1 y0
q2 q1 q3
q2 y0
q3 q0 q2
q3 y1
Graf automatu
Funkcja przejść
G =
0
(q
0
1
(z
1
q
1
2
(z
0
q
2
3
(z
1
q
3
4
(z
0
q
0
, z
1
q
2
)
4
, z
0
q
1
)
3
, z
1
q
0
)
2
, z
0
q
3
)
1
)
0
Wyniki testu dla słowa 11011
Q(t) Z(t) Q(t+1) Y(t+1)
Wyniki testu dla słowa 110110
Q(t) Z(t) Q(t+1) Y(t+1)
q0 z1 q1 y0
q0 z1 q1 y0
q1 z1 q0 y0
q1 z1 q0 y0
q0 z0 q3 y1
q0 z0 q3 y1
q3 z1 q2 y0
q3 z1 q2 y0
q2 z1 q3 y1
q2 z1 q3 y1
q3 z0 q0 y0
1
Alfabet wejść: Z = {z0 – 0, z1 – 1}
2. Automat sprawdzający, czy zadany ciąg jest w formie: 110...0....011
Alfabet wyjść: Y = {y0 – ciąg nie jest w zadanej formie, y1 – ciąg jest w zadanej formie}
Alfabet wewnętrzny: Q = {q0, q1, q2, q3, q4, q5, q6}
Tabela przejść
Tabela wyjść
Z
Q
z0 z1
Q Y
q0 q6 q1
q0 y0
q1 q6 q2
q1 y0
q2 q3 q6
q2 y0
q3 q3 q4
q3 y0
q4 q6 q5
q4 y0
q5 q6 q6
q5 y1
q6 q6 q6
q6 y0
Graf automatu
Funkcja przejść
G =
0
(q
0
1
(z
1
q
1
2
(z
1
q
2
3
(z
0
q
3
4
(z
0
q
3
, z
1
q
4
5
(z1q5
6
(z1q6, z0q6
7
(z0q6, z1q6)
7
)
6
, z0q6)
5
)
4
,
z0q6)
2
, z0q6)
1
)
0
Wyniki testu dla słowa 1100011
Q(t) Z(t) Q(t+1) Y(t+1)
Wyniki testu dla słowa 1100111
Q(t) Z(t) Q(t+1) Y(t+1)
q0 z1 q1 y0
q0 z1 q1 y0
q1 z1 q2 y0
q1 z1 q2 y0
q2 z0 q3 y0
q2 z0 q3 y0
q3 z0 q3 y0
q3 z0 q3 y0
q3 z0 q3 y0
q3 z1 q4 y0
q3 z1 q4 y0
q4 z1 q5 y1
q4 z1 q5 y1
q5 z1 q6 y0
2
Alfabet wejść: Z = {z0 – 0, z1 – 1}
3. Analizator składniowy liczby
a) Wariant z E – automat akceptuje liczby zapisane poprawnie w notacji naukowej
Alfabet wejść: Z = {z0 – cyfra(0...9), z1 – kropka, z2 – E, z3 – znak(+/-)}
Alfabet wyjść: Y = {y0 – liczba niepoprawna, y1 – liczba poprawna}
Alfabet wewnętrzny: Q = {q0, q1, q2, q3, q4, q5, q6, q7, q8}
Tabela przejść
Tabela wyjść
Z
Q
z0 z1 z2 z3
Q Y
q0 q2 q8 q8 q1
q0 y0
q1 q2 q8 q8 q8
q1 y0
q2 q8 q3 q8 q8
q2 y0
q3 q4 q8 q8 q8
q3 y0
q4 q4 q8 q5 q8
q4 y0
q5 q7 q8 q8 q5
q5 y0
q6 q7 q8 q8 q8
q6 y0
q7 q7 q8 q8 q8
q7 y1
q8 q8 q8 q8 q8
q8 y0
Graf automatu
Funkcja przejść
G =
0
(q
0
1
(z
3
q
1
2
(z
0
q
2
3
(z
1
q
3
4
(z
0
q
4
5
(z
0
q
4
, z
2
q
5
6
(z
3
q
6
7
(z
0
q
7
8
(z
0
q
7
, z
1
q
8
, z
2
q
8
, z
3
q
8
9
(z
0
q
8
, z
1
q
8
,
z
2
q
8
, z
3
q
8
)
9
)
8
, z
1
q
8
, z
2
q
8
, z
3
q
8
)
7
, z
0
q
7
, z
1
q
8
, z
2
q
8
)
6
, z
1
q
8
, z
3
q
8
)
5
, z
1
q
8
, z
2
q
8
, z
3
q
8
)
4
, z
0
q
8
, z
2
q
8
,
z
3
q
8
)
3
, z
1
q
8
, z
2
q
8
, z
3
q
8
)
2
, z
0
q
2
, z
1
q
8
, z
2
q
8
)
1
)
0
3
Wyniki testu dla słowa -4.25E-23
Q(t) Z(t) Q(t+1) Y(t+1)
Wyniki testu dla słowa 4.25+23
Q(t) Z(t) Q(t+1) Y(t+1)
q0 z3 q1 y0
q0 z0 q2 y0
q1 z0 q2 y0
q2 z1 q3 y0
q2 z1 q3 y0
q3 z0 q4 y0
q3 z0 q4 y0
q4 z0 q4 y0
q4 z0 q4 y0
q4 z3 q8 y0
q4 z2 q5 y0
q8 z0 q8 y0
q5 z3 q6 y0
q8 z0 z8 y0
q6 z0 q7 y1
q7 z0 q7 y1
b) Wariant bez E – automat akceptuje poprawnie zapisane liczby rzeczywiste
Alfabet wyjść: Y = {y0 – liczba niepoprawna, y1 – liczba poprawna}
Alfabet wewnętrzny: Q = {q0, q1, q2, q3, q4, q5}
Tabela przejść
Tabela wyjść
Z
Q
z0 z1 z2
Q Y
q0 q2 q5 q1
q0 y0
q1 q2 q5 q5
q1 y0
q2 q2 q3 q5
q2 y0
q3 q4 q5 q5
q3 y0
q4 q4 q5 q5
q4 y1
q5 q5 q5 q5
q5 y0
Graf automatu
4
Alfabet wejść: Z = {z0 – cyfra(0...9), z1 – kropka, z2 – znak(+/-)}
Funkcja przejść
G =
0
(q
0
1
(z
0
q
2
, z
2
q
1
2
(z
0
q
2
3
(z
0
q
2
, z
1
q
3
4
(z
0
q
4
5
(z
0
q
4
, z
1
q
5
, z
2
q
5
6
(z
0
q
5
, z
1
q
5
, z
2
q
5
)
6
)
5
, z
1
q
5
,
z
2
q
5
)
4
, z
2
q
5
)
3
, z
1
q
5
, z
2
q
5
)
2
, z
1
q
5
)
1
)
0
Wyniki testu dla słowa -43.25
Q(t) Z(t) Q(t+1) Y(t+1)
Wyniki testu dla słowa 43.25+2
Q(t) Z(t) Q(t+1) Y(t+1)
q0 z2 q1 y0
q0 z0 q2 y0
q1 z0 q2 y0
q2 z0 q2 y0
q2 z0 q2 y0
q2 z1 q3 y0
q2 z1 q3 y0
q3 z0 q4 y1
q3 z0 q4 y1
q4 z0 q4 y1
q4 z0 q4 y1
q4 z2 q5 y0
q5 z0 q5 y0
4. Wnioski
Ćwiczenie polegające na abstrakcyjnej syntezie, a następnie komputerowej symulacji
automatów skończonych Moore'a, pozwoliło nam na poznanie podstawowych sposobów
projektowania ich oraz działania. Dla każdego przedstawionego automatu przeprowadziliśmy
syntezę abstrakcyjną, polegającą na określeniu alfabetów: wejściowego, wyjściowego
i przejść, sporządzeniu tabel: przejść oraz wyjść i narysowaniu grafu. Następnie zapisaliśmy
funkcję przejść w sposób odpowiadający wymaganiom programu do symulacji automatów.
Poprawność wyznaczonej funkcji mogliśmy sprawdzić, porównując grafy – nasz
i wygenerowany przez aplikację.
Po procesie syntezy, przeszliśmy do symulacji i testów automatów. Podając na wejście
automatu odpowiednio dobrane słowa wejściowe, sprawdzaliśmy, czy jego wyjście
przyjmuje wartość przez nas oczekiwaną. Wszystkie zaprojektowane automaty działają
poprawnie, choć żadnego z nich nie udało nam się w całości uruchomić na zajęciach –
mieliśmy problemy z odpowiednim zapisem funkcji przejścia.
5
Plik z chomika:
kaqus
Inne pliki z tego folderu:
LUC-spr11.pdf
(128 KB)
LUC-spr9.pdf
(182 KB)
LUC-spr7.pdf
(77 KB)
LUC-spr5.pdf
(153 KB)
LUC-spr4.pdf
(149 KB)
Inne foldery tego chomika:
Języki programowania
Laboratorium podstaw fizyki
Teoria sygnałów
Zgłoś jeśli
naruszono regulamin