logika 207.pdf

opracował: dr hab. inż. Jan Magott

e-version: dr inż. Tomasz Kapłon

INSTYTUT CYBERNETYKI TECHNICZNEJ POLITECHNIKI WROCŁAWSKIEJ

ZAKŁAD SZTUCZNEJ INTELIGENCJI I AUTOMATÓW

Ćwiczenia laboratoryjne z Logiki Układów Cyfrowych

ćwiczenie 207

temat: AUTOMATY MOORE’A I MEALY

1. CEL ĆWICZENIA

Celem ćwiczenia jest zapoznanie studentów z dwoma podstawowymi kategoriami

automatów oraz metodami transformacji automatu Moore’a w automat Mealy

i odwrotnie.

2. PROGRAM ĆWICZENIA

1. Synteza automatów Moore’a i Mealy realizujących zadane przekształcenie

2. Transformacja automatu Moore’a w automat Mealy i odwrotnie

3. PROBLEMATYKA ĆWICZENIA

Automaty Moore’a i Mealy są automatami z pamięcią realizującymi przekształcenie

sekwencji (ciągów liter) wejściowych w sekwencje wyjściowe.

Automaty te rozpoczynają swoje działanie w stanie początkowym. Następnie,

kolejno podawane litery alfabetu wejściowego powodują zmianę stanu automatu oraz

generację liter alfabetu wyjściowego.

Badane kategorie automatów różnią się sposobem generacji liter alfabetu

wyjściowego. W przypadku automatu Moore’a, litera generowana na wyjściu zależy od

aktualnego stanu. Automat Mealy wytwarza literę na wyjściu na podstawie stanu,

w którym została podana litera alfabetu wejściowego oraz na podstawie tej litery.

Porównajmy automaty Moore’a i Mealy realizujące identyczne przekształcenie

zbioru sekwencji wejściowych w zbiór sekwencji wyjściowych. Ponadto zakładamy, że

oba automaty są w postaci minimalnej. Przy podanych wymaganiach, automat

Moore’a posiada nie mniejszą liczbę stanów niż automat Mealy.

4. WIADOMOŚCI PODSTAWOWE

4.1 Definicje automatu Moore’a i Mealy

Automatem skończonym nazywamy dyskretny przetwornik informacji

przekształcający sekwencje wejściowe w sekwencje wyjściowe, w sposób z góry

zadany. Zbiór Z liter alfabetu wejściowego, zbiór Y liter alfabetu wyjściowego oraz

zbiór Q stanów wewnętrznych są zbiorami skończonymi – stąd nazwa automatu.

Automat pracuje w dyskretnej skali czasu, przy czym punkty tej skali mogą być

ponumerowane kolejnymi liczbami naturalnymi. Symbolem z(t) ∈ Z oznaczamy literę

podaną na wejście automatu w punkcie t dyskretnej chwili czasu. W podobny sposób

interpretowane są symbole q(t) ∈ Q, y(t) ∈ Y.

opracował: dr hab. inż. Jan Magott

e-version: dr inż. Tomasz Kapłon

Definicja 1

Automat skończony typu Mealy jest szóstka uporządkowaną:

A = < Z, Q, Y, Φ, Ψ, q 0 >,

gdzie:

Z – alfabet wejściowy,

Q – zbiór stanów,

Y – alfabet wyjściowy,

Φ : Z x Q → Q – funkcja przejść określająca zmiany stanów,

Ψ : Z x Q → Y – funkcja wyjść wyznaczająca literę generowaną na wyjściu,

q 0 – stan początkowy.

Funkcja przejść określa stan q(t+1) = Φ(z(t), q(t)), który osiągnie automat po

podaniu na jego wejście liter z(t), jeśli litera ta została podana w stanie q(t).

Funkcja wyjść definiuje literę alfabetu wyjściowego:

y(t) = Ψ(z(t), q(t))

generowaną na wyjściu, jeśli w stanie q(t) podano na wejście literę z(t).

Interpretacja graficzna obu funkcji zawarta została na rysunku 1.

q (t)

z(t)/y(t)

q (t+1)

rysunek 1

Definicja 2

Automat skończony typu Moore’a jest szóstka uporządkowaną:

A = < Z, Q, Y, Φ, Ψ, q 0 >,

gdzie składowe Z, Q, Y, Φ oraz q 0 określone są identycznie jak dla automatu Mealy,

zaś Ψ: Q → Y jest funkcją wyjść.

Funkcja wyjść określa literę: y(t) = Ψ(q(t)) generowaną przez automat po osiągnięciu

stanu q(t).

Funkcję przejść i wyjść automatu Moore’a zilustrowane są na rysunku 2.

y(t)

y(t+1)

q (t)

z(t)

q (t+1)

rysunek 2

4.2 Transformacja między automatami Moore’a i Mealy

Niech X* będzie zbiorem wszystkich sekwencji skończonej długości utworzonych

z liter alfabetu X wraz ze słowem pustym.

Symbolem /Ψ oznaczamy uogólnioną funkcję wyjść automatu /Ψ : Z* x Q → Y*.

Wartość tej funkcji /Ψ(/z, q) jest sekwencją wyjściową /y ∈ Y* generowaną w wyniku

podania sekwencji /z ∈ Z* na wejście automatu znajdującego się w stanie q.

opracował: dr hab. inż. Jan Magott

e-version: dr inż. Tomasz Kapłon

Definicja 3

Dwa automaty A 1 = < Z, Q 1 , Y, Φ 1 , Ψ 1 , q 01 > oraz A 2 = < Z, Q 2 , Y, Φ 2 , Ψ 2 , q 02 >

nazywamy równoważnymi jeśli dla każdej sekwencji /Z ∈ Z* spełniona jest równość:

Ψ 1 (/z, q 01 ) = /Ψ 2 (/z, q 02 )

Twierdzenie 1

Dla danego automatu Moore’a A 1 = < Z, Q 1 , Y, Φ 1 , Ψ 1 , q 01 > istnieje równoważny

automat Mealy A 2 = < Z, Q 2 , Y, Φ 2 , Ψ 2 , q 02 > takie, że:

Q 2 = Q 1 , Φ 2 = Φ 2 Ψ 2 (z ,q) = Ψ 1 ( Φ 1 (z, q)), q 02 = q 01 .

Transformację automatu Moore’a w automat Mealy zobrazujemy postacią

graficzną.

Przykład 1

Niechdanybędzie automat Moore’a, jak na rysunku 3.

z 2

q 0

y 1

z 1

q 1

y 2

z 1

z 2

z 1

z 2

q 2

y 2

q 3

y 1

rysunek 3

Równoważny mu automat Mealy pokazany na rysunku 4.

z 2 y 1

q 0

z 1 y 2

q 1

z 1 y 1

z 2 y 2

z 1 y 1

z 2 y 2

q 2

q 3

rysunek 4

opracował: dr hab. inż. Jan Magott

e-version: dr inż. Tomasz Kapłon

Przeanalizujmy przykładowe wartości funkcji przejść i wyjść obu automatów.

Niech w stanie q 0 automatu Moore’a, na wejściu pojawi się litera z 1 . W tym

przypadku dla funkcji przejść mamy Φ 1 (z 1 , q 0 ) = q 1 . Zatem Φ 1 (z 1 , q 0 )= q 2 . ponadto

dla funkcji wyjść prawdziwa jest równość Ψ 1 (q 1 ) = y 2 , a więc Ψ 2 (z 1 , q 0 ) = y 2 .

W przypadku transformacji automatu Mealy w automat Moore’a często wymagane

jest zwiększenie liczby stanów. Rozważmy fragment grafu automatu Mealy

ilustrowany rysunkiem 5a).

y j

y r

q k

q s

q t

z i y j

z i

z p y r

z p

rysunek 5

Stanowi q k automatu Mealy nie można przypisać tylko jednego stanu automatu

Moore’a bowiem stan taki musiałby po osiągnięciu go w wyniku podania na wejście

litery z i generować literę y j , natomiast po osiągnięciu tego stanu poprzez podanie

litery z p musiałby generować literę y r . W tym przypadku stan q k automatu Mealy

zostanie odwzorowany w dwa stany automatu Moore’a odpowiadające parom

uporządkowanym <q k , y j > oraz <q k , y r >. Stany te można oznaczyć symbolami q s i q t

- rysunek 5b).

Przykład 2

z 2 y 2

z 1 y 1

q 1

z 2 y 2

q 0

z 2 y 1

z 3 y 1

z 1 y 1

q 2

z 3 y 1

rysunek 6

opracował: dr hab. inż. Jan Magott

e-version: dr inż. Tomasz Kapłon

Wynikiem transformacji automatu Mealy z rysunku 6 jest automat Moore’a

pokazany na rysunku 7.

z 3

y 1

z n2

y 1

z 1

z 3

y 2

z 2

z 1

z 2

z 3

z 1

y 2

z 1

z 3

y 2

z 3

z 3

y 1

z 3

rysunek 7

Stan przyporządkowany parze <q 2 , y 2 > może być wyeliminowany, bowiem nie może

on być osiągnięty z żadnego ze stanów odpowiadających parom <q 0 , y 1 >, <q 0 , y 2 >.

Twierdzenie 2

Dla danego automatu Mealy A 1 = < Z, Q 1 , Y, Φ 1 , Ψ 1 , q 01 > istnieje równoważny

mu automat Moore’a A 2 = < Z, Q 2 , Y, Φ 2 , Ψ 2 , q 02 > zdefiniowany następująco:

Q 2 = Q 1 x Y,

Φ 2 : Z x Q 2 → Q 2 taka, że Φ 2 (z, <q, y) =< Φ 1 (z, q), Ψ 1 (z, q)>, gdzie q ∈ Q 1 ,

Ψ 2 : Q 1 x Y → Y takie, że Ψ2 (<q, y>) = y,

q 20 jest jednym ze stanów <q 01 , y>, gdzie y ∈ Y.

4.3 Minimalizacja automatu

W celu uzyskania automatu z minimalną liczbą stanów, należy wykryć stany

równoważne i zastąpić je jednym stanem.

Każdy z rozpatrywanym dotąd automatów charakteryzuje się tym, że w każdym

z jego stanów może pojawić się na wejściu, każda z liter alfabetu wejściowego.

Istnieją automaty, dla których w pewnych stanach podane mogą być na wejście tylko

litery z podzbioru Z. Jeśli na wejściu automatu w stanie q 1 nie może być podana

litera a j , wówczas stosujemy następujące oznaczenie dla funkcji przejść Φ(z j , q j ) = -.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: