18 - Konečné automaty (jazyky přijímané jazyky KA, varianty KA, minimalizace KA, Mihill-Nerodova věta))

Question 1

Definice nedeterministického KA

Answer 1

NKA je 5-ice M = (Q, Σ, δ, q₀, F)
• Q – konečná množina stavů
• Σ – konečná vstupní abeceda
• δ – funkce přechodu (zobrazení Q × Σ → 2^Q)
○ To je 2^Q je potenční množina, tedy množina, která obsahuje všechny podmnožiny množiny Q.
○ konečná množina pravidel tvaru: pa → q,​kde p, q∈Q, a∈Σ
• q₀ – počáteční stav (q₀∈Q)
• F – množina koncových stavů (F⊆Q)

Je-li δ : Q × Σ → Q ∪ {nedef.}, (tedy |δ(q, a)| = 1) jedná se o deterministicý konečný automat. Automat lze také reprezentovat graficky nebo tabulkou.

Jazyky přijímané KA jsou jazyky třídy 3 Chomského hierarchie (regulární jazyky).

Question 2

Základní pojmy KA (konfigurace, přechody, přijímaný jazyk, rozlišitelné stavy)

Answer 2

Konfigurace = Dvojice (q, w)∈Q×Σ* tj. stav a zbývající vstup
Počáteční konfigurace = Dvojice (q₀, w) tj. počáteční stav a celý vstup
Koncová konfigurace = Dvojice (q ∈ F, ε) tj. některý koncový stav a prázdný vstup

Přechod ⊢
• Změna jedné konfigurace na jinou jednou aplikací funkce přechodu (přečtení jednoho znaku ze vstupu a změna stavu)
• ⊢ᵏ – k přechodů po sobě
• ⊢⁺ – libovolný počet přechodů (> 0) (tranzitivní uzávěr relace přechodu)
• ⊢* – libovolný počet přechodů (tranzitivní a reflexivní uzávěr relace přechodu)

Jazyk přijímaný KA
• L(M)={w|(q₀, w)⊢* (q, ε)∧q∈F}
• tj. množina všech řetězců pro které KA přejde z počáteční do koncové konfigurace

Rozlišitelné stavy
• Stavy jsou rozlišitelné pokud existuje nějaký vstupní řetězec pro který automat z jednoho stavu skončí v koncovém stavu a z druhého ne.
• Formálně: Stavy p, q jsou rozlišitelné pokud ∃ w∈Σ:(p, w)⊢ (p₁, ε)∧(q, w)⊢*(q₁, ε) a právě jeden z p₁, q₁ je v F.

Question 3

Varianty konečných automatů (Rozšířený KA)

Answer 3

Liší se definice funkce přechodu δ: (Q × (Σ ∪{ε})→2^Q, tj. je rozšířený o ε-přechody.

Question 4

Varianty konečných automatů (Deterministický konečný automat (DKA))

Answer 4

Liší se definice funkce přechodu δ:Q×Σ→Q∪{nedef}, nedef ∉ Q, tj. pro každou konfiguraci existuje jen jeden možný přechod.

• Jsou ekvivalentní NKA
• Každý NKA lze převést na DKA

Question 5

Varianty konečných automatů (úplný, bez nedosažitelných stavů, dobře specifikovaný)

Answer 5

Úplný DKA
Funkce přechodu je definována pro všechny kombinace vstupního znaku a stavu. tj. δ je totální funkcí na Q × Σ.

Pro případy, kdy neúplný KA nemohl pokračovat (a tím odmítl vstup) zavádíme speciální nekoncový stav ERROR (SINK, T, …) do kterého, když se automat dostane tak jej nemůže opustit (tj. po přečtení celého vstupu je stále v nekoncovém stavu a tak vstup odmítne).

DKA bez nedosažitelných stavů - Je DKA ve kterém eliminujeme nedosažitelné stavy. To jsou ty stavy, do kterých se nedá z počátečního stavu dostat.

Dobře specifikovaný KA
• JeÚKA
• Nemá nedostupné stavy
• Má max jeden neukončující stav!

Question 6

Minimální/redukovaný DKA (MDKA)

Answer 6

Minimální DKA
Je DKA bez nedosažitelných stavů ve kterém nejsou žádné 2 stavy nerozlišitelné:
1. Redukujeme nerozlišitelné stavy (cyklus: do množiny dostupných stavů přidáme všechny stavy do kterých se dá libovolným symbolem přejít z některého dostupného stavu z minulého kroku)
2. Odstraníme přebytečné stavy (stavy nemající vliv na přijímání vstupního řetězce)
3. V minimálním DKA jsou stavy množiny stavů z původního automatu, pričemž v každé množině jsou stavy navzájem nerozlišitelné (jde v podstatě o třídy ekvivalence vzhledem k relaci nerozlišitelnosti).

Minimalizace KA
Stručný postup:
1. ε uzávěr, odstranění ε přechodů
2. Odstranění nedeterminismu
3. Odstranění nedostupných stavů
4. Odstranění nerozlišitelných stavů

Převod NKA na DKA
- pro všechny možné stavy S DKA a všechny možné znaky a na vstupu určíme následující stav jako sjednocení všech stavů do kterých vedou přechody se znakem a ze stavů v množině S. Pokud žádné takové přechody neexistují je přechod nedefinovaný.

Question 7

Myhill-Nerodova věta

Answer 7

Myhill-Nerodova věta
1. Nechť L je jazyk nad Σ, pak následující tvrzení jsou ekvivalntní:
○ L je jazyk přijímaný deterministickým konečným automatem.
○ L je sjednocení některých tříd rozkladu určeného pravou kongruencí na Σ* s konečným indexem.
○ Relace ~L má konečný index.
2. Počet stavů libovolného minimálního deterministického konečného automatu přijímajícího L je roven indexu ~L (takový DKA existuje právě tehdy, když ~L je konečný)
Každý konečný jazyk je regulární (opak neplatí).