2. Konečné deterministické a nedeterministické automaty a jejich vztah k regulárním jazykům, regulární výrazy

Question 1

Konečné automaty

Answer 1

Konečné automaty jsou matematické modely, které se používají k rozpoznání jazyků

Jazyky jsou množiny řetězců tvořených symboly z nějaké abecedy

Konečné automaty mají konečný počet stavů

Konečný automat pracuje tak, že přijímá vstupní řetězce

Postupuje symbol po symbolu a při každém kroku přechází ze stavu do stavu podle předem daných pravidel

Question 2

Konečné deterministické automaty (DFA)

Answer 2

Konečné deterministické automaty jsou takové konečné automaty, které mají přesně jeden možný přechod pro každý symbol vstupního řetězce a pro každý stav

Každému stavu automatu odpovídá právě jeden další stav, do kterého se automat při přijetí určitého symbolu dostane

Přechodová funkce DFA
- Funkce, která pro každý stav a symbol abecedy definuje následující stav
- Tuto funkci lze reprezentovat tabulkou nebo grafem
- Koncové stavy jsou stavy, ve kterých se automat zastaví po přijetí vstupního řetězce

Question 3

Konečné nedeterministické automaty (NFA)

Answer 3

Rozdíl je, že umožňují více možností přechodu ze stavu do stavu pro daný symbol vstupní abecedy

To znamená, že pro každou dvojici stavu a symbolu vstupní abecedy může existovat více než jeden následující stav

Při použití NFA se vstupní řetězec postupně čte, ale v každém kroku může automat přejít do jednoho z několika stavů podle daných pravidel

NFA se skládá z množiny stavů, vstupní abecedy, přechodové funkce, startovního stavu a množiny koncových stavů

Přechodová funkce NFA
- Definována stejně jako u DFA, ale pro každou dvojici stavu a symbolu může vracet více než jeden následující stav

Question 4

Vztah k regulárním jazykům

Answer 4

DFA a NFA jsou matematické modely, které se používají k rozpoznávání REGULÁRNÍCH jazyků

Regulární jazyky jsou formální jazyky, které mohou být generovány regulárními výrazy, nebo přijímány konečnými automaty

Každý regulární jazyk lze rozpoznat konečným automatem

Pro každý regulární jazyk existuje konečný automat, který tento jazyk přijímá

DFA a NFA jsou dva způsoby, jak popsat konečné automaty
- DFA se používá pro popis deterministických konečných automatů
- NFA se používá pro popis nedeterministických konečných automatů

Oba tyto automaty jsou ekvivalentní, což znamená, že každý NFA lze převést na ekvivalentní DFA a naopak => stejný jazyk lze rozpoznat pomocí DFA i NFA
Přestože jsou DFA a NFA ekvivalentní, NFA jsou obecně jednodušší na konstrukci a porozumění než DFA. To znamená, že pro některé problémy může být snadnější vytvořit skrze NFA než DFA

Question 5

Regulární výrazy

Answer 5

Regulární výrazy jsou matematickým popisy regulárních jazyků

Regulární výrazy se používají pro vyhledávání textových řetězců nebo zpracování dat v řetězcové formě

Skládají se z několika primitivních symbolů a operátorů, které umožňují popsat různé vlastnosti řetězců

Základní primitivní symboly jsou jednotlivá písmena a číslice, které představují samotné znaky v řetězci

Obsahují i několik operátorů, které umožňují vytvořit složitější výrazy pomocí kombinace primitivních symbolů

NAPŘÍKLAD nad abecedou {a, b}:
(a+b)(a+b) {aa, ab, ba, bb}
(a + b)^2 {aa, ab, ba, bb}
(a + b)* všechny řetězce nad abecedou {a, b}
(a + b)^k všechny řetězce nad abecedou {a, b}
délce k o ab nula a více a, následováno nula a více b
a + ab {a, ab} o a(a + b) {aa, ab}