(163797) Sylwia Starzyńska
(163769) Michał Luszawski
Temat: Komputerowa realizacja automatów skończonych
(laboratorium dnia 23.10.2008)
Cel ćwiczenia
Praktyczne zapoznanie się ze sposobem programowej realizacji na komputerze automatów skończonych (na przykładzie automatu typu Moore'a). Postać symboliczna grafu automatu i jej reprezentacja w pamięci komputera.
Specyfikacje techniczne
Oprogramowanie specjalistyczne do realizacji automatów skończonych.
Wstęp teoretyczny
Automaty skończone to automaty z skończonym alfabetem liter wejściowych oraz skończonym alfabetem liter wyjściowych. Skończony automat Moore'a opisany jest funkcjami:
Q x X - > Q (funkcja przejść)
Q - > Y (funkcja wyjść)
Punktem wyjścia do programowej realizacji automatu Moore'a jest transformacja grafu automatu na wyrażenie symboliczne. Zadany jest automat Moore'a reprezentowany przez:
Alfabet wejściowy (oznaczony jako Z)
Alfabet wyjściowy (Y)
Zbiór stanów wewnętrznych (Q)
Funkcja przejść (wyrażenie opisujące realizowany graf)
Funkcja wyjść
Stan początkowy (qi)
Graf automatu Gi jest transformowany na wyrażenie symboliczne G+i . Składa się ono z wyszczególnionych iloczynów qizj (q- stan następny, z - litera generująca przejście). Przykładowy sposób realizacji podany zostanie w zadaniach poniżej. Graf jest rysowany w momencie zatwierdzenia wyrażenia symbolicznego w programie.
Aby przygotować symulację należy określić:
Stan początkowy automatu
Realizowane słowo (ciąg liter alfabetu wejściowego)
Następnie rozpoczynamy symulację:
Symulacja krokowa
Symulacja ciągła
Poprzez użycie klawisza SPACE możemy obserwować poszczególne kroki symulacji (dla symulacji krokowej). W okienku obok wypisywane są dane dotyczące: stanu obecnego (Q(t)) oraz następnego (Q(t+1)), a także zmiennej realizującej to przejście (x(t)) wraz z literą odebraną na wyjściu (Y(t+1)).
Realizowane ćwiczenia
Zad.1
Przykładowy graf.
Alfabet wejściowy Z= {z1, z2}
Alfabet wyjściowy Y= { y1 , y2 , y3 }
Zbiór stanów wewnętrznych Q={ q1 , q2 , q3, q4 }
Funkcja przejść : {G+i = 0(q2 1( z1 q32( z1 q1 3( z2,q2 , z1 q3 )3 , z2 q3) 2 , z2q4 2( z2 q1, z1q4 ) 2) 1) 0 }
Funkcja wyjść :
q1 → y2
q2 → y3
q3 → y1
q4 → y3
Rysunek 1.
Q(t) |
x(t) |
Q(t+1) |
Y(t+1) |
q1 |
z2 |
q2 |
y3 |
q2 |
z1 |
q3 |
y1 |
q3 |
z1 |
q1 |
y2 |
q1 |
z1 |
q3 |
y1 |
q3 |
z2 |
q3 |
y1 |
Symulacja.
Stan początkowy q1
Słowo wejściowe : z2, z1,z1, z1,z2
Zad 2.
Zamek szyfrowy.
Alfabet wejściowy Z= {z1, z2, z3}
Alfabet wyjściowy Y= { y1 , y2}
Zbiór stanów wewnętrznych Q={ q1 , q2 , q3 , q4 , q5 }
Funkcja przejść : {G+i = 0(q1 1(z2 q5, z3 q5, z1q2 2( z1q5, z3q5, z2q3 3( z1 q5, z2 q5, z3q44(z1 q4, z2 q4, z3 q4 ) 3) 2)1, q51(z1 q5, z2 q5, z3 q5)1)0 }
Funkcja wyjść :
q1 → y1
q2 → y1
q3 → y1
q4 → y1
q5 → y2
Rysunek 2.
Q(t) |
x(t) |
Q(t+1) |
Y(t+1) |
q1 |
z1 |
q2 |
y1 |
q2 |
z2 |
q3 |
y1 |
q3 |
z2 |
q5 |
y2 |
q5 |
z1 |
q5 |
y2 |
Symulacja.
Stan początkowy q1
Słowo wejściowe : z1, z2, z2, z1.
(włączy się alarm)
Zad 3.
Sumator szeregowy.
Alfabet wejściowy Z= {z1, z2, z3, z4}
Alfabet wyjściowy Y= { y1 , y2}
Zbiór stanów wewnętrznych Q={ q1 , q2 , q3 , q4 }
Funkcja przejść : {G+i = 0(q1 1(z1 q1, z2 q2, z3q2 , z4 q3 2( z1q2, z2q3, z3q3, z4 q4 3( z2q3, z3 q3, z4q4, z1q24(z1 q1, z2 q2, z3 q2, z4 q3) 3) 2)1)0 }
Funkcja wyjść :
q1 → y1
q2 → y2
q3 → y1
q4 → y2
Rysunek 3.
Q(t) |
x(t) |
Q(t+1) |
Y(t+1) |
q1 |
z3 |
q2 |
y2 |
q2 |
z2 |
q2 |
y2 |
q2 |
z4 |
q3 |
y1 |
q3 |
z3 |
q3 |
y1 |
q3 |
z1 |
q2 |
y2 |
Symulacja.
Stan początkowy q1
Słowo wejściowe : z3, z2, z4, z3, z1 .
5. Wnioski
Komputer wraz zainstalowanym odpowiednim oprogramowaniem, jest idealnym narzędziem do symulacji działania automatów skończonych. Dzięki komputerowej symulacji bada się poprawność działania modelu automatu (stworzonego w postaci grafu).
Na podstawie funkcji przejść otrzymujemy gotowy graf automatu, który później możemy zasymulować, sprawdzając tym samym poprawność jego działania.