(163797) Sylwia Starzyńska

(163769) Michał Luszawski

Temat: Komputerowa realizacja automatów skończonych

(laboratorium dnia 23.10.2008)

1. 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.

2. Specyfikacje techniczne

Oprogramowanie specjalistyczne do realizacji automatów skończonych.

3. 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 (q_i)

Graf automatu G_i jest transformowany na wyrażenie symboliczne G⁺_i . Składa się ono z wyszczególnionych iloczynów q_iz_j (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)).

4. Realizowane ćwiczenia

Zad.1

Przykładowy graf.

• Alfabet wejściowy Z= {z_1, z₂}

• Alfabet wyjściowy Y= { y1 , y2 , y3 }

• Zbiór stanów wewnętrznych Q={ q1 , q2 , q3, q4 }

• Funkcja przejść : {G⁺_i = ⁰(q2 ¹( z1 q3²( z1 q1 ³( z2,q2 , z1 q3 )³ , z2 q3) ² , z2q4 ²( z2 q1, z1q4 ) ²) ¹) ⁰ }

• 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 q₁

Słowo wejściowe : z_2, z₁,z_1, z₁,z₂

Zad 2.

Zamek szyfrowy.

• Alfabet wejściowy Z= {z_1, z₂, z₃}

• Alfabet wyjściowy Y= { y1 , y2}

• Zbiór stanów wewnętrznych Q={ q1 , q2 , q3 , q4 , q5 }

• Funkcja przejść : {G⁺_i = ⁰(q1 ¹(z2 q5, z3 q5, z1q2 ²( z1q5, z3q5, z2q3 ³( z1 q5, z2 q5, z3q4⁴(z1 q4, z2 q4, z3 q4 ) ³) ²)¹, q5¹(z1 q5, z2 q5, z3 q5)¹)⁰ }

• 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 q₁

Słowo wejściowe : z_1, z₂, z_2, z₁.

(włączy się alarm)

Zad 3.

Sumator szeregowy.

• Alfabet wejściowy Z= {z_1, z₂, z_3, z₄}

• Alfabet wyjściowy Y= { y1 , y2}

• Zbiór stanów wewnętrznych Q={ q1 , q2 , q3 , q4 }

• Funkcja przejść : {G⁺_i = ⁰(q1 ¹(z1 q1, z2 q2, z3q2 , z4 q3 ²( z1q2, z2q3, z3q3, z4 q4 ³( z2q3, z3 q3, z4q4, z1q2⁴(z1 q1, z2 q2, z3 q2, z4 q3) ³) ²)¹)⁰ }

• 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 q₁

Słowo wejściowe : z_3, z₂, z_4, z_3, z₁ .

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.

---