Konečné Automaty Flashcards
(8 cards)
1
Q
Typy konečných automatů
A
- rozpoznávací automat - o vstupním řetězci vydává rozhodnutí typu ano/ne
- klasifikační automat – vstupní řetězec zařadí do jedné z n tříd
- automat s výstupní funkcí (překladový automat) – na základě vstupního řetězce vytvoří výstupní řetězec z výstupních symbolů
2
Q
Typy konečných automatů s výstupní funkcí a rozdíly mezi nimi
A
- Mealy - výstupní posloupnost je určena posloupností přechodů, kterými automat při zpracování řetězce prošel
- Moore - výstupní posloupnost je určena posloupností stavů, kterými automat při zpracování řetězce prošel
- Důsledek: při zpracování vstupního řetězce délky n
- Mealy – výstupní řetězec má délku n
- Moore - výstupní řetězec má délku n + 1
3
Q
Rozpoznávací konečný automat – definice
A
A=(Q,Σ,δ,q0,F)
- Q je konečná neprázdná množina stavů
- Σ je konečná neprázdná množina vstupních symbolů
- q0∈Q je počáteční stav
- δ:Q×Σ→Q je přechodová funkce
- F⊆Q je množina koncových stavů
4
Q
Klasifikační konečný automat – definice
A
A=(Q,Σ,δ,q0,{Qi})
- Q je konečná neprázdná množina stavů
- Σ je konečná neprázdná množina vstupních symbolů
- q0∈Qje počáteční stav
- δ:Q×Σ→Q je přechodová funkce
- {Qi} je rozklad množiny stavů
5
Q
Konečný automat s výstupní fcí Mealyho typu – definice
A
A=(Q,Σ,O,δ,q0,λ)
- Q je konečná neprázdná množina stavů
- Σ je konečná neprázdná množina vstupních symbolů
- O je konečná neprázdná množina výstupních symbolů
- q0∈Q je počáteční stav
- δ:Q×Σ→Q je přechodová funkce
- λ:Q×Σ→O je výstupní funkce
6
Q
Konečný automat s výstupní fcí Mooreova typu – definice
A
A=(Q,Σ,O,δ,q0,λ)
- Q je konečná neprázdná množina stavů
- Σ je konečná neprázdná množina vstupních symbolů
- O je konečná neprázdná množina výstupních symbolů
- q0∈Q je počáteční stav
- δ:Q×Σ→Q je přechodová funkce
- λ:Q→O je výstupní funkce
7
Q
Vlastnosti konečného automatu
A
- konečný počet stavů
- konečný počet vstupních symbolů
- následující stav je jednoznačně určen stavem a vstupním symbolem
- jednoznačně určený počáteční stav
8
Q
Konfigurace konečného automatu
A
Uspořádaná dvojice (stav, dosud nezpracovaná část vstupního řetězce)
