Quartz 4

Automat

3 min read

Definice- Máme neprázdnou množinu znaků Σ (abeceda):

  • Slovo (řetězec) je libovolná posloupnost znaků ze Σ.

  • Prázdné slovo se značí λ (neobsahuje žádné znaky)

  • Množina všech slov v abecedě Σ se značí Σ*.

  • Jazyk je libovolná podmnožina L ∈ Σ*

  • Délka slova w se značí |w| (počet znaků).

  • počet výskytů znaku z ve slově w značíme |w|z.

Deterministický automat

Nedeterministický automat

Konečný automat je matematický model výpočtu používaný k reprezentaci a analýze systémů s omezenou pamětí. Používá se hlavně v teorii jazyků, návrhu kompilátorů, regulárních výrazech a modelování systémů.

Definice konečného automatu

Konečný automat je abstraktní výpočetní model, který se skládá z:

  1. Konečné množiny stavů (Q)

    QQ

  2. Vstupní abecedy (Σ) – množina symbolů, které může automat číst

    Σ\Sigma

  3. Přechodové funkce (δ:Q×Σ→Q) – určuje, do jakého stavu automat přejde při čtení určitého symbolu

    δ:Q×Σ→Q\delta: Q \times \Sigma \to Q

  4. Počátečního stavu (q0​∈Q)

    q0∈Qq_0 \in Q

  5. Množiny koncových stavů (F⊆Q) – určuje, kdy automat přijme vstupní řetězec

    F⊆QF \subseteq Q

Automat čte vstupní řetězec znak po znaku, přechází mezi stavy podle přechodové funkce a na konci rozhodne, zda řetězec patří do jazyka, který rozpoznává.

Typy konečných automatů

  1. Deterministický konečný automat (DFA - Deterministic Finite Automaton)

    • V každém kroku může existovat jen jeden možný přechod pro daný vstup.

    • Lze efektivně implementovat a používat např. v regulárních výrazech.

  2. Nedeterministický konečný automat (NFA - Nondeterministic Finite Automaton)

    • Pro jeden symbol může existovat více možných přechodů nebo žádný.

    • Může obsahovat epsilon přechody (ε), což znamená, že může přejít do jiného stavu i bez čtení znaku.

      ε\varepsilon

    • I když vypadá silnější než DFA, pro každý NFA existuje ekvivalentní DFA.

Příklad DFA

Automat, který přijímá binární čísla dělitelná 3:

  • Stavy: Q={q0​,q1​,q2​} (označují zbytek dělení 3)

    Q={q0,q1,q2}Q = {q_0, q_1, q_2}

  • Abeceda: Σ={0,1}

    Σ={0,1}\Sigma = {0,1}

  • Počáteční stav: q0​

    q0q_0

  • Koncový stav: q0​ (označuje, že číslo je dělitelné 3)

    q0q_0

  • Přechody:

    • q0q_0q0​ + 0 → q0​, q0​ + 1 → q1​

      q0q_0

      q0q_0

      q1q_1

    • q1q_1q1​ + 0 → q2​, q1​ + 1 → q0​

      q2q_2

      q1q_1

      q0q_0

    • q2q_2q2​ + 0 → q1​, q2​ + 1 → q2​

      q1q_1

      q2q_2

      q2q_2

Pokud zadáme např. “110”, skončíme ve stavu q0q_0q0​, takže automat přijme vstup.

Vztah k regulárním jazykům

  • Konečné automaty jsou ekvivalentní regulárním jazykům (dle Kleeneho věty).

  • Jakýkoli jazyk rozpoznatelný DFA lze popsat regulárním výrazem.

  • NFA i DFA rozpoznávají pouze regulární jazyky (nic složitějšího).

K čemu se konečné automaty používají?

  • Lexikální analýza (část kompilátorů)

  • Regulární výrazy a jejich implementace (např. v grep, sed, regex knihovnách)

  • Modelování jednoduchých systémů (výdejní automaty, řízení procesů)

  • Kontrola a verifikace systémů (např. protokoly v počítačových sítích)

Konečné automaty jsou základním konceptem teoretické informatiky a slouží jako základ pro složitější modely výpočtu, jako jsou zásobníkové automaty (pro bezkontextové jazyky) nebo Turingovy stroje (pro obecné výpočty).

Graph View

Backlinks