TECHNIKA CYFROWA I MIKROKOMPUTERY

WYKŁAD 7

10.04.2003

UKŁADY SYNCHRONICZNE

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

UKŁAD SEKWENCYJNY jest to 
urządzenie służące do 
przetwarzania informacji 
cyfrowej. Przedstawić go można 
w postaci bloku posiadającego n-
sygnałów wejściowych x

1

, x

2

, ... 

x

n

 oraz m sygnałów wyjściowych 

y

1

, y

2

, ... y

m

. Wektor wartości 

binarnych sygnałów wejściowych 
x

1

, x

2

,...,x

n

 określa tzw. stan wejść 

automatu
(a

1

, a

2

,...,a

n

)=X

i

gdzie a

i

 - wartość zmiennej x

i

UKŁAD 

SEKWENCYJNY

x

1

x

2

x

n

y

1

y

2

y

n

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Zbiór stanów wejść automatu 
X={x

1

, x

2

,...,x

n

}

nazywany jest alfabetem wejściowym, a poszczególne stany 
-literami tego alfabetu.
Podobnie wartości sygnałów wyjściowych y

1

,...,y

n

 określają stan 

wyjść automatu
(b

1

,...,b

m

)=Y

j

,

gdzie b

i

 - wartość zmiennej y

i

,

a zbiór stanów wyjść
Y={y

1

, y

2

,...,y

n

}

nazywany jest alfabetem wyjściowym. Ponieważ nie wszystkie 
kombinacje sygnałów wejściowych i wyjściowych muszą 
występować więc moc zbioru X jest nie większa niż 2

n

, zaś moc 

zbioru Y nie większa niż 2

m

.

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

W układach kombinacyjnych aktualny stan wyjść Y

t

 zależał 

jedynie od aktualnego stanu wejść X

t

Y

t

=f(X

t

)

W układach sekwencyjnych aktualny stan wyjść zależy również 
od poprzednich stanów wejść
Y

t

=f(X

t

, X

t-1

, X

t-2

, ...)

Mówimy zatem, że automat sekwencyjny ma pamięć. Dla 
opisania automatu sekwencyjnego wprowadza się pojęcie 
stanu wewnętrznego A, określonego przez stany Q

i

 elementów 

pamięciowych automatu
A=(Q

1

,...,Q

i

,...Q

k

)

Zbiór stanów wewnętrznych automatu oznaczamy:
A={A

1

, A

2

,...,A

k

} 

Moc A jest nie większa niż 2

k

.

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Związki pomiędzy stanem wyjść, stanem wewnętrznym i stanem 
wyjść automatu opisane są funkcjami przejść i wyjść. Funkcja 
przejść dla danego stanu wewnętrznego i stanu wejść automatu 
określa jego następny stan wewnętrzny
A

t+1

=(A

t

, X

t

)

Funkcja wyjść określa stan wyjść automatu. Stan ten może zależeć 
od stanu wewnętrznego i stanu wejść (tzw. Automat Mealy’ego)
Y

t

=

1

(A

t

, X

t

)

bądź też, jak często bywa w praktyce, tylko od stanu 
wewnętrznego (tzw. Automat Moore’a)
Y

t

=

2

(A

t

)

Jak widać do scharakteryzowania działania automatu wystarczy 
znać X, Y, A, , .
Automat skończony określa się jako uporządkowaną piątkę:
M=<X

M

, Y

M

, A

M

, 

M

, 

M

>

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT MEALY’EGO

Stan wyjścia zależy od stanu 
wewnętrznego i od stanu wejść





X

Y

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT MOORE’A

Stan wyjścia zależy jedynie od 
stanu wewnętrznego





X

Y

A

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

W zależności od sposobu oddziaływania sygnałów wejściowych na 
stan pamięci automatu dzielimy automaty sekwencyjne na 
synchroniczne i asynchroniczne. W układach synchronicznych stan 
wejść X może oddziaływać na układ pamięciowy (to znaczy zmieniać 
stan) tylko w ściśle określonych momentach, wyznaczonych 
sygnałem na specjalnym wejściu taktującym (zegarowym). Dowolny 
układ sekwencyjny można traktować jak układ synchroniczny, jeżeli 
jeden z sygnałów wejściowych g spełnia następujące warunki:
• zmiana stanu wewnętrznego układu następuje przy określonej 
zmianie (np. z 1 na 0) sygnału g,
• pozostałe sygnały wejściowe zmieniają swą wartość gdy g=0 
(warunek ten jest konieczny dla niektórych typów przerzutników)
Sygnał g uznajemy wówczas za sygnał taktujący. Sygnał ten, zwany 
także taktem, narzuca rytm pracy układu i jest przyjmowany za 
umowną jednostkę czasu. Symbole t, t+1 ... oznaczają więc kolejne 
takty zegara.

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

W układach asynchronicznych nie wyróżnia się wejścia 
taktującego, zmiana stanu wewnętrznego następuje 
bezpośrednio pod wpływem zmiany stanu wejść. Nowy stan 
wewnętrzny A

t+1 

ustala się po czasie , wyznaczonym przez 

opóźnienie elementów, z których zbudowany jest automat. 
Funkcję przejść automatu asynchronicznego można więc

 

zapisać w postaci:
A(t+)= [A(t), X(t)]

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Funkcje przejść i wyjść automatu są zwykle przedstawiane w 
postaci tablicy, zwanej tablicą przejść i wyjść. Z lewej strony 
tablicy wypisane są wszystkie stany wewnętrzne automatu, a u 
góry - wszystkie stany wejść. W klatkach tablicy dla każdego 
stanu wewnętrznego A

it 

i dla każdego stanu wejść X

jt 

podany 

jest następny stan wewnętrzny 
A

pt+1

= (A

jt

, X

jt

). Stany wyjść automatu Mealy’ego wygodnie jest 

wpisywać w klatkach tej samej tablicy.

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT MEALY’EGO

A

1

A

3

A

4

A

2

x

1

/y

3

x

2

/y

3

x

2

/y

4

x

2

/y

1

x

1

/y

1

x

2

/y

2

x

1

/y

3

x

1

/y

1

X

t

A

t

X

1

X

2

A

1

A

3

Y

1

A

4

Y

3

A

2

A

1

Y

3

A

2

Y

4

A

3

A

4

Y

1

A

4

Y

2

A

4

A

2

Y

3

A

3

Y

1

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT MOORE’A

A

1

A

3

A

4

A

2

x

1

x

2

x

1

x

1

x

2

x

2

x

1

(Y

1

)

(Y

2

)

(Y

3

)

(Y

4

)

X

t

A

t

X

1

X

2

A

1

A

2

A

4

Y

2

A

2

A

2

A

3

Y

1

A

3

A

3

A

1

Y

1

A

4

A

2

A

2

Y

3

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

W przypadku automatu Moore’a stan wyjść jest jednakowy dla 
wszystkich klatek znajdujących się w danym wierszu, 
wypisujemy go więc z prawej strony tablicy.
Dokładnym odpowiednikiem tablicy przejść jest graf automatu. 
Wierzchołkom grafu przypisuje się numery stanów 
wewnętrznych A, natomiast łukom - stany wejść X. Symbole 
odpowiadające stanom wyjść Y umieszcza się w przypadku 
automatu Mealy’ego przy łukach, a w przypadkach automatu 
Moore’a przy wierzchołkach. 

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

PRZYKŁAD 1

Licznik liczący sygnały taktowe 
modulo 5 (to znaczy po pięciu 
impulsach wracający do stanu 
początkowego). Licznik taki ma 
pięć stanów wewnętrznych 
A

1

,...,A

5

, w każdym takcie układ 

przechodzi do kolejnego stanu.

A

t

A

t+1

Y

A

1

A

2

Y

1

A

2

A

3

Y

2

A

3

A

4

Y

3

A

4

A

5

Y

4

A

5

A

1

Y

5

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

PRZYKŁAD 1

Y

1

A

1

A

1

A

1

A

1

A

1

Y

5

Y

2

Y

4

Y

3

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

PRZYKŁAD 2

Układ, który przy podaniu 
sygnału 1 na wejście x wytwarza 
na wyjściu y pojedynczy, nie 
ucięty impuls o długości równej 
okresowi generatora C.

A

t

A

t+1

Y

A

1

A

2

Y

1

A

2

A

3

Y

2

A

3

A

4

Y

3

A

4

A

5

Y

4

A

5

A

1

Y

5

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

PRZYKŁAD 3

Komparator szeregowy, 
porównujący ze sobą dwie liczby 
binarne C i D (podawane na wejścia 
szeregowo, cyfra po cyfrze, 
poczynając od najmniej znaczących) 
będzie miał trzy stany wewnętrzne 
odpowiadające trzem możliwym 
przypadkom C>D, C=D,C<D. W 
stanach tych zapamiętywane są 
wyniki porównania dotychczas 
podanych fragmentów liczb. 
Kombinacje sygnałów wyjściowych 
x

1

x

2

 00, 01, 11, 10 odpowiadają 

stanom wejścia x

00

, x

01

, x

11

, x

10. 

Sygnały wyjściowe y

1

y

2

 równe 10, 

00 lub 01 będą odpowiadać 
poszczególnym stanom 
wewnętrznym (automat Moore’a)

X/A X

00

X

01

X

11

X

10

Y

1

Y

2

1

1

3

1

2

00

2

2

3

3

2

10

3

3

3

3

2

01

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

PRZYKŁAD 3

3

C<D

00
11

00
11
01

01

01

2

C>D

1

C=D

01

10

00
11
01

10

00

10

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

PRZYKŁAD 4

Sumator szeregowy, służący do 
dodawania dwu liczb 
podawanych kolejni cyfra po 
cyfrze (poczynając od najmniej 
znaczącej), powinien mieć dwa 
stany wewnętrzne. Stany te 
odpowiadają wartościom 
przeniesienia (p=0 lub p=1) do 
pozycji bardziej znaczącej.

X/A

X

1

00

X

2

01

X

3

11

X

4

10

A

1

A

1

0

A

1

1

A

2

0

A

1

1

A

2

A

1

1

A

2

0

A

2

1

A

2

0

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

PRZYKŁAD 4

A

1

p=0

11 (0)

A

1

p=1

00 (1)

00 (0)

01
10

(1)

10
01

(0)

11(1)

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Dla prostych układów synchronicznych graf lub tablicę przejść 
można narysować bezpośrednio na podstawie słownego opisu 
działania układu. W grafach i tablicach nie wyróżnia się wśród 
sygnałów wejściowych stanu zegara a jedynie zaznacza się 
stan wejść automatu (w momencie zmiany stanu sygnału 
zegarowego). Momentem tym może być zmiana stanu zegara 
z 1 na 0 (tylne zbocze zegara) lub z 0 na 1 (przednie zbocze 
zegara). Moment zmian nie wpływa na sposób opisu i metodę 
syntezy automatu, ale ma pewne znaczenie dopiero na eapie 
syntezy logicznej.  

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

W podanych przykładach zakładano dowolnie, że układ ma być 
autoamtem Moore;a lub Mealy’ego. Na ogół trudno określić czy 
prostszą realizację ma automat Mealy’ego, czy równoważny 
mu automat Moore’a. Równoważność automatów rozumie się 
tu w sensie ich takiego samego działania obserwowanego z 
zewnątrz (to znaczy obserwacji jedynie stanów wejść i wyjść). 

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Zmianę tablicy przejść automatu Mealy’ego w tablicę przejść 
równoważnego mu automatu Moore’a można przeprowadzić w 
następujący sposób:
• każdej parze stanów (A

j

, Y

j

) wpisanych w klatki tablicy 

automatu Mealy’ego przyporządkować stan B

j

 automatu 

Moore’a, przy czym jednakowym parom powinny odpowiadać 
jednakowe stany B

j

• ułożyć tablice przejść automatu Moore’a, przypisując 
każdemu stanowi B

j

 sygnał wyjściowy Y

j

 z odpowiadającej mu 

pary (A

j

, Y

j

). Stany następne, dla każdego X

i

, przypisujemy 

stanowi B

j

=(A

j

, Y

j

) takie jakie miał stan A

j

 z tejże pary, to 

znaczy (

1

(A

j

, X

i

), (A

j

, X

i

))=B

r

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

X

1

X

2

A

1

A

2

  (B

1

)

0

A

3

 (B

2

)

0

A

2

A

4

 (B

3

)

0

A

5

 (B

4

)

0

A

3

A

6

 (B

5

)

0

A

7

 (B

6

)

0

A

4

A

1

 (B

7

)

0

A

1

 (B

8

)

1

A

5

A

1

 (B

8

)

1

-

A

6

A

1

 (B

8

)

1

-

A

7

A

1

 (B

7

)

0

-

X

1

X

2

Y

B

1

B

3

B

4

0

B

2

B

5

B

6

0

B

3

B

7

B

8

0

B

4

B

8

-

0

B

5

B

8

-

0

B

6

B

7

-

0

B

7

B

1

B

2

0

B

8

B

1

B

2

1

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Zmiana tablicy przejść automatu Moore’a w tablicę przejść 
automatu Mealy’ego polega na wpisaniu w kratkę tablicy, w 
któej występowa stan następny A

j

, wartości wyjścia automatu 

Moore’a odpowiadającego temu stanowi, a następnie usunięcie 
kolumny wyjść

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

X

00

X

01

X

10

X

11

Y

1

Y

2

A

1

A

1

A

3

A

1

A

2

00

A

2

A

2

A

3

A

2

A

2

10

A

3

A

3

A

3

A

3

A

2

01

X

00

X

01

X

10

X

11

A

1

A

1

00

A

3

00

A

1

00

A

2

00

A

2

A

2

10

A

3

10

A

2

10

A

2

10

A

3

A

3

01

A

3

01

A

3

01

A

2

01

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Dane są dwa automaty skończone zupełne
N=< X

N

, Y

N

, A

N

, 

N

, 

N

>

M=<X

M

, Y

M

, A

M

, 

M

, 

M

>

takie, że X

N

=X

M

, Y

N

=Y

M

.

Niech p=x

1

, x

2

,...,x

s

 będzie pewnym ciągiem stanów wejść 

automatu.
Można określić dla automatu funkcje (A

1

, p), (A

1

, p), ’(A

1

, p), 

(A

1

, p). (A

1

, p)=A

2

, A

3

,...,A

s+1

, gdzie A

2

, A

3

,...,A

s+1

 jest ciągiem 

stanów wewnętrznych takich, że:
A

2

= (A

1

,X

1

),...,A

s+1

=(A

s

,X

s

)

Funkcja (A

1

,p) określa ciąg stanów, przez które przechodzi 

automat znajdujący się początkowo w stanie wewnętrznym A

1

, 

gdy na wejście podamy ciąg stanów wejść p=X

1

, X

2

,...,X

s

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

(A

1

, p)=Y

1

, Y

2

,...,Y

s

gdzie Y

1

, Y

2

,...,Y

s

, jest ciągiem stanów wyjścia takich, że:

Y

1

=(A

1

, X

1

)

Y

2

=(A

2

, X

2

)= ((A

1

, X

1

), X

2

)

...
Y

s

=(A

s

, X

s

)= (A

s

,X

s

)

Funkcja (A

1

, p) określa ciąg wyjść, którym automat znajdujący 

się początkowo w stanie A

1

 odpowiada na ciąg stanów do 

wejścia p=X

1

, X

2

,...,X

s

. Wartością funkcji ’(A

1

, p) jest A

s+1

, to 

znaczy stan, do którego przejdzie automat ze stanu A

1

 pod 

wpływem ciągu p=X

1

, X

2

,...,X

s

. Wartością funkcji (A

1

, p) jest 

ostatni stan ciągu wyjściowego wygenerowanego przez 
automat znajdujący się początkowo w stanie A

1

, po podaniu 

ciągu wejściowego p. 

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

(3, X

1

X

2

)= 1 2

(3, X

1

X

1

X

1 

)= 1 3 1

(4, X

2

X

1

X

1

)= 5 4 2

’(3, X

1

X

2

)= 2

’(3, X

1

X

1

X

1 

)= 1

’(4, X

2

X

1

X

1

)= 2

(3, X

1

X

2

)=1 1

(3, X

1

X

1

X

1 

)= 1 0 1

(4, X

2

X

1

X

1

)= 0 0 1

(3, X

1

X

2

)=1

(3, X

1

X

1

X

1 

)= 1

(4, X

2

X

1

X

1

)= 1

X

1

X

2

A

1

3
0

2
1

A

2

3
0

2
1

A

3

1
1

5
0

A

4

2
1

5
0

A

5

4
0

6
1

A

6

4
0

5
1

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Powiemy, że automaty zupełne M i N o takich samych 
alfabetach X i Y są równoważne (M  N), gdy dla każdego 

ciągu p podanego na wejścia automatów i dla każdego stanu 
A

i

A

N

, istnieje taki stan A

j 

A

M

, że odpowiednie ciągi wyjściowe 

obu automatów są jednakowe.
Stany A

i

 oraz A

j

 automatu M są równoważne gdy dla każdego 

ciągu wejściowego p odpowiednie ciągi wyjściowe są 
jednakowe. Do wyszukiwania stanów równoważnych 
wykorzystuje się następujące twierdzenie.

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Dwa stany wewnętrzne A

i

, A

j

 automatu w pełni określonego są 

równoważne, jeżeli dla dowolnego stanu wejść X

r

 spełnione są 

następujące warunki:
• sygnały wyjściowe, odpowiadające obu tym stanom są 
jednakowe
• stany następne są jednakowe lub równoważne

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Stany 1 i 2 są równoważne, gdyż 
ich następniki (stany następne) 
są jednakowe, to znaczy:

(1, X

1

)= (2, X

1

)= 3

(1, X

2

)= (2, X

2

)= 3

(1, X

1

)= (2, X

1

)= 0

(1, X

2

)= (2, X

2

)= 1

Stany 3 i 4 są równoważne, gdyż 
ich następniki są jednakowe lub 
równoważne

(3, X

1

)= 1 (4, X

1

)= 2 12

(3, X

2

)= (4, X

2

)= 5

(3, X

2

)= (4, X

2

)= 0

X

1

X

2

A

1

3
0

2
1

A

2

3
0

2
1

A

3

1
1

5
0

A

4

2
1

5
0

A

5

4
0

6
1

A

6

4
0

5
1

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Analizując równoważność stanów 5 i 
6 można zauważyć, że
(5, X

1

)= (6, X

1

), (5, X

1

)= (6, X

1

)

(5, X

2

)= (6, X

2

)

czyli stany 5 i 6 są równoważne pod 
warunkiem, że stany 
(5, X

2

)= 6 i (6, X

2

)= 5 są 

równoważne. Te stany są 
równoważne, gdyż pod wpływem 
stanu wejścia X

2

 automat dla obu 

tych stanów da  wyjście 1 i przejdzie 
do stanu 5 lub 6, a dla stanu wejścia 
X

1

 przejdzie do stany 4. Zatem dla 

dowolnego ciągu wejściowego 
automat znajdujący się w stanie 5 i 
w stanie 6 wygeneruje taki sam ciąg 
wyjściowy.

X

1

X

2

A

1

3
0

2
1

A

2

3
0

2
1

A

3

1
1

5
0

A

4

2
1

5
0

A

5

4
0

6
1

A

6

4
0

5
1

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Ponieważ automat zachowuje się 
tak samo dla różnych stanów 
równoważnych, każdą z par 
stanów równoważnych można ze 
sobą połączyć i otrzymany 
automat będzie równoważny 
automatowi początkowemu. 
Połączone stany 1 i 2 oznaczono 
przez A, stany 3 i 4 przez B, zaś 
stany 5 i 6 przez C. Stany A i C 
okazują się równoważne, zatem 
automat można zminimalizować.

X

1

X

2

A

1

3
0

2
1

A

2

3
0

2
1

A

3

1
1

5
0

A

4

2
1

5
0

A

5

4
0

6
1

A

6

4
0

5
1

X

1

X

2

A

B

0

A

1

B

A

1

C

0

C

B

0

C

1

X

1

X

2

K

L

0

L

1

L

K

1

K

0

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT SEKWENCYJNY

Zdefiniowana relacja równoważności stanów automatu jest 
przechodnia (A

1

 A

2

  A

2

 A

3

A

1

 A

3

), zwrotna (A A) oraz 

symetryczna 
(A

1

 A

2

 A

2

 A

1

), czyli jest znaną z teorii relacji relacją 

równoważności, dzielącą zbiór A na rozłączne podzbiory, 
których suma jest równa A.
Relacja równoważności stanów dzieli zbiór stanów automatu na 
zbiory stanów wzajemnie równoważnych, które mogą być 
zastąpione jednym stanem.

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT NIEZUPEŁNY

Ciąg p=X

1

X

2

...X

n 

jest stosowalny do automatu niezupełnego 

będącego w stanie A

1

, jeśli wszystkie elementy ciągu (A

1

, p) 

są określone, to znaczy jeżeli stan ’(A

1

, p) jest określony dla 

każdego podciągu początkowego p’  ciągu p. 

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT NIEZUPEŁNY

Ciąg X

1

X

1

 jest stosowalny do 

automatu znajdującego się w 
stanie 2, nie jest natomiast 
stosowalny do tego automatu, 
znajdującego się w stanie 4, gdyż 
stan (4, x

1

) jest nieokreślony. Dwa 

stany wewnętrzne automatu 
niezupełnego A

i

,A

j

 są niesprzeczne 

jeśli są one jednakowe lub co 
najmniej jeden z nich jest 
nieokreslony. Dwa stany wyjśćia 
y

1

,y

2

,...,y

m

 i y

1

’,y

2

’,...,y

m

’ są 

niesprzeczne, gdy każda para y

i

,y

i

 

zawiera dwa elementy jednakowe 
(0 i 0 lub 1 i 1) lub co najmniej 
jeden nieokreślony (0 i -, 1 i -, - i -)
Niesprzeczne są więc na przykład 
stany wyjśc 10 i 10 1- i 10,-0- i 10- 

X

1

X

2

X

3

X

4

Y

1

3

3

-

2

0-

2

3

-

-

1

-1

3

2

4

5

1

11

4

-

4

4

-

01

5

3

-

-

1

1-

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT NIEZUPEŁNY

Dla celów minimalizacji wprowadza się w automatach 
niezupełnych pojęcie stanów zgodnych. Powiemy, że stany A

i

 i 

A

j

 są zgodne, jeżeli dla każdego ciągu wejściowego 

p=X

1

,X

2

,...,X

s

, który jest stosowalny zarówno do A

i 

jak i do A

j

 

stany końcowe wygenerowanych przez p ciągów wyjściowych 
są niesprzeczne. Relację zgodności stanów A

i

 i A

j

 oznaczymy 

przez A

i

A

j

.

Do znajdowania stanów zgodnych wygodnie jest posłużyć się 
następującym twierdzeniem:

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT NIEZUPEŁNY

Dwa stany wewnętrzne A

i

, A

j

 automatu niezupełnego są 

zgodne, gdy spełnione są następujące warunki:
• sygnały wyjściowe odpowiadające obu tym stanom są 
niesprzeczne,
• stany następne są niesprzeczne lub zgodne

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT NIEZUPEŁNY

Stany 1 i 2 są zgodne, gdyż
(1, X

1

)= (2, X

1

)= 3

(1, X

2

)= 3 (2, X

2

)= -

(1, X

3

)= - (2, X

3

)= -

(1, X

4

)= 2 (2, X

4

)= 1

(1)= 0 - 
(2)= - 1
Stany 1 i 2 odpowiadają na każdy 
ciąg wejść, dla którego istnieje 
określony ciąg stanów 
wewnętrznych i wyjść, takim 
samym ciągiem stanów wyjścia. 
Podobnie można stwierdzić, że 
stany 2 i 3 są zgodne ze sobą. 
Relacja zgodności nie jest 
przechodnia, gdyż stany 1 i3 nie są 
zgodne, bo mają sprzeczne wyjścia.

X

1

X

2

X

3

X

4

Y

1

3

3

-

2

0-

2

3

-

-

1

-1

3

2

4

5

1

11

4

-

4

4

-

01

5

3

-

-

1

1-

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT NIEZUPEŁNY

Badając stany 3 i 5 zauważamy, 
że mają niesprzeczne wyjścia (11 
i 1-)
(3, X

4

)= (5, X

4

)= 1

(3, X

3

)= 5, (5, X

3

)= -

(3, X

2

)= 4, (2, X

2

)= -

(3, X

1

)= 2, (2, X

1

)= 3

(1)= 0 - 
(2)= - 1
Stany 1 i 1,5 i - oraz 4 i - są 
niesprzeczne. Natomiast ze 
względu na kolumnę X

1

 stany 3 i 

5 są zgodne pod warunkiem, że 
stany 2 i 3 są zgodne. Stany 2 i 3 
są zgodne, więc 3 i 5 też są 
zgodne.

X

1

X

2

X

3

X

4

Y

1

3

3

-

2

0-

2

3

-

-

1

-1

3

2

4

5

1

11

4

-

4

4

-

01

5

3

-

-

1

1-

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT NIEZUPEŁNY

W pierwotnej tablicy przejść  
zgodne są stany 5 i 6, gdyż 
odpowiadają im jednakowe 
wyjścia i jednakowe stany 
następne. Podobnie zgodne są 
stany 4 i 7. Po zastąpieniu 
zgodnych par stanów przez inny 
stan (piszemy 5 zamiast 5 i 6 
oraz 4 zamiast 4 i 7, jeżeli w 
danej kolumnie występuje 
symbol i kreska - piszemy ten 
symbol

X

1

X

2

A

1

2
0

3
0

A

2

4
0

5
0

A

3

6
0

7
0

A

4

1
0

1
1

A

5

1
1

-

A

6

1
1

-

A

7

1
0

-

X

1

X

2

A

1

2
0

3
0

A

2

4
0

5
0

A

3

5
0

4
0

A

4

1
0

1
1

A

5

1
1

-

TECHNIKA CYFROWA I MIKROKOMPUTERY

AUTOMAT NIEZUPEŁNY

W wielu przypadkach nie da się zminimalizować tablicy przejść 
w tak prosty sposób. Na następnym wykładzie zostanie podana 
metoda minimalizacji liczby stanów wewnętrznych automatu, 
tzw. metoda par. Metoda ta jest stosowana zarówno do 
automatów zupełnych jak i niezupełnych.