bpc-los_11 - Speciální čítače, KSA

– L1 = {a, bb, bc, ac}
– L2 = {abc, bca, cba}

• Konečný jazyk obsahuje konečný počet slov.
• Nekonečný jazyk obsahuje nekonečně mnoho 

slov.

Rozpoznávací KSA

• Tento KSA si lze představit bez výstupu 

(rozpoznávací, klasifikační automat). Výstupem je 
defakto vnitřní stav.

• Umožňuje přijmout nebo zamítnout předané slovo.

A = (Q, Σ, δ, q0, F)

Q  množina vnitřních stavů
Σ  množina vstupních symbolů
δ  stavově přechodová funkce 
q0 počáteční vnitřní stav
F  množina koncových stavů

Rozpoznávací KSA

• Použití:

– Rozpoznávání řetězců (patřících do formálního 

jazyka).

– Detekce chyb v posloupnosti symbolů.

Překladové KSA

• KSA s výstupem
• Na posloupnost vstupních symbolů reaguje 

posloupností symbolů výstupní abecedy

A = (Q, Σ, O, δ, q0, λ)

– Mealyho KSA

• Výstupní symbol je určen stavem a symbolem na vstupu.

– Mooreův KSA

• Výstupní symbol je určen pouze stavem.

Q  množina vnitřních stavů
Σ  množina vstupních symbolů
O  množina výstupních symbolů
δ  stavově přechodová funkce 
q0 počáteční vnitřní stav
λ  výstupní funkce

Konečný stavový automat jako model 


sekvenčního logického obvodu

• KSA je abstraktním modelem sekvenčního 

logického obvodu.

• Symboly a stavy jsou kódovány pomocí 

kombinací binárních signálů. 

– Např. pro dva signály x2, x1 jsou možné 4 symboly: 


{0, 0}, {0, 1}, {1, 0}, {1, 1}.

Synchronní a asynchronní automaty

• Mezi současným a následujícím vnitřním stavem 

musí existovat časový odstup.

• Asynchronní automaty

– Časový odstup mezi stavy je důsledkem pouze zpoždění 

vnitřních obvodů vytvářejících stavové signály.

– Mění svůj vnitřní stav (s malým zpožděním) po změně 

vstupního stavu.

• Synchronní automaty

– Okamžik změny vnitřního stavu je určen synchronizačními 

impulsy (hodinovými impulsy), které jsou přivedeny na 
klopné obvody. 

Signály a stavy v sekvenčním obvodu

Y

X

Q

Vnitřní stav

Výstupní stav

Vstupní stav

signály:

signály:

signály:

xN

xN−1

⋮

x0

yM

yM−1

⋮

y0

qR

qR−1

⋮

q0

Přechodová funkce

• Závislost následujícího vnitřního stavu Qt+1 

na aktuálním vnitřním stavu Qt a vstupním 
stavu Xt :

Qt+1 = δ(Qt, Xt)

δ  stavově přechodová funkce

Výstupní funkce

• V obecném případě je výstupní funkce