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

Je třeba zhodnotit zda daná situace je nebo není na 
závadu:

• Hazardy není potřeba řešit => následující blok je 

synchronní s CLK. 

• Hazardy je nutné řešit => následující blok není 

synchronní. (Na výstupy přidáme záchytné registry, 
který zajistí jejich změny synchronně s CLK, ale také je 
zpozdí o jednu periodu hodinového signálu CLK.)

Konečné stavové automaty - 

teorie

Konečný stavový automat

• Nejobecnějším modelem každého sekvenčního 

obvodu je 

konečný stavový automat - má konečný 

počet vstupních stavů, výstupních stavů a vnitřních 
stavů. 

• Za stav je brána kombinace hodnot signálů. V 

technické praxi pracujeme se signály binárními, 
kterých je vždy konečný počet. Proto i počet možných 
kombinací hodnot těchto signálů je také konečný.

• Každou kombinaci označujeme kvůli úspornosti 

písmenem / symbolem.

Konečný stavový automat

• Konečný stavový automat 


   (KSA, KA, FSM - Finite State Machine)

• Teoretický výpočetní model používaný v informatice 

(např. při studiu formálních jazyků).

• Popisuje velice jednoduchý počítač, který může být 

v jednom z několika vnitřních stavů. 

• Mezi stavy přechází na základě symbolů čtených 

ze vstupu (vstupních symbolů).

• Množina stavů (vstupu, výstupu i vnitřních) je

konečná (odtud název).

• KSA si pamatuje pouze vnitřní stav.

Symbol, abeceda

• Symbol (znak, signál)

– Atomická dále nedělitelná jednotka, se kterou pracujeme.

• Písmeno, číslice, logická hodnota 0 a 1, ...

• Abeceda

– Libovolná konečná neprázdná množina symbolů.
– Budeme ji značit Σ.
– Příklady abeced:

• Binární abeceda: Σ = { 0, 1 }.
• Abeceda pro celá čísla: Σ = { +, -, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }.

Slovo

• Libovolná konečná posloupnost symbolů 

dané abecedy.

• Vzniká zřetězením symbolů dané abecedy.

– Např. pro abecedu Σ = { 0, 1 } můžeme vytvářet 

slova: 0, 1, 00, 01, 10, 11, 000, ..., 1011, ....

• Délka slova je počet symbolů, které slovo 

tvoří.

– Např. slovo 1011 má délku 4.

Formální jazyk

• Formální jazyk (dále jen jazyk) nad abecedou Σ je 

libovolná množina slov vytvořených nad 
abecedou Σ.

• Jazyk značíme písmenem 

L.

• Např. jazyky nad Σ = {a, b, c} :