4.2 Překladové automaty

Překladový automat je stroj, který ze vstupu čte řetězce z jazyka definičního oboru a k nim vytváří odpovídající překlad z jazyka oboru hodnot.

Konečný překladový automat

Definice (Konečný překladový automat)

Konečný překladový automat

(Nedeterministický) konečný překladový automat (KPA) je uspořádaná šestice \(KPA = (Q, \Sigma, D, \delta, q_0, F)\), kde:

• \(Q\) je konečná neprázdná množina stavů,
• \(\Sigma\) je konečná množina vstupních symbolů,
• \(D\) je konečná množina výstupních symbolů,
• \(\delta\) je přechodová funkce definována jako zobrazení z \(Q \times (\Sigma \cup \{\varepsilon\})\) do množiny konečných podmnožin množiny \(Q \times D^*\),
• \(q_0 \in Q\) je počáteční stav,
• \(F \subseteq Q\) je množina koncových stavů.

Přechodovou funkci můžeme znázornit dvěma způsoby:

• Formální zápis:

  \[\delta(S, a) = \{(A, x)\}\]

  (ze stavu \(S\) na symbol \(a\) jdeme do stavu \(A\) a na výstup dáme symbol \(x\))

• Ohodnocený orientovaný graf (stavový diagram): Vše je stejné jako u normálního konečného automatu. Pouze rozšíříme ohodnocení hran mezi stavy o výstup:

  

Definice (Deterministický konečný překladový automat)

Deterministický konečný překladový automat

Deterministický konečný překladový automat (DKPA) je takový KPA, kde pro všechny stavy \(q \in Q\) platí jedna z následujících podmínek:

• \((\forall a \in \Sigma : |\delta(q, a)| \le 1) \land \delta(q, \varepsilon) = \emptyset\)
• \((\forall a \in \Sigma : \delta(q, a) = \emptyset) \land |\delta(q, \varepsilon)| \le 1\)

Vysvětlení determinismu

KPA nazveme deterministickým, když buď nemá \(\varepsilon\)-přechody a pro každý stav jsou všechny odchozí přechody odlišitelné symbolem, který je čten ze vstupu, nebo má \(\varepsilon\)-přechody, ale pokud z nějakého stavu vede \(\varepsilon\)-přechod, poté z něj nevede žádný jiný.

Překlad definovaný konečným překladovým automatem

• Řetězce skládající se ze vstupních symbolů, které automat přijme, tvoří definiční obor.
• Naopak řetězce tvořící obor hodnot jsou složené z výstupních symbolů, které automat pošle na výstup při přijímání nějakého řetězce z definičního oboru.

Řetězec \(x\) z oboru hodnot je překladem řetězce \(w\) z definičního oboru právě tehdy, když automat přijme řetězec \(w\) a přitom na výstup pošle řetězec \(x\).

Mealyho a Mooreův automat

Speciálními případy konečných překladových automatů jsou Mealyho a Mooreův automat. Tyto automaty nemají koncové stavy a výstup je vázán buď na přechod (Mealy), nebo na stav (Moore).

Definice (Mealyho automat)

Mealyho automat

Mealyho automat definujeme jako šestici \(M = (Q, \Sigma, D, \delta, \lambda, q_0)\), kde:

• \(Q\) je konečná neprázdná množina stavů,
• \(\Sigma\) je konečná množina vstupních symbolů,
• \(D\) je konečná množina výstupních symbolů,
• \(\delta : Q \times \Sigma \to Q\) je přechodová funkce,
• \(\lambda : Q \times \Sigma \to D\) je výstupní funkce (vázána na přechod; parciální funkci zde nepřipouštíme),
• \(q_0 \in Q\) je počáteční stav.

Definice (Mooreův automat)

Mooreův automat

Mooreův automat definujeme jako šestici \(M = (Q, \Sigma, D, \delta, \lambda, q_0)\), kde:

• \(Q\) je konečná neprázdná množina stavů,
• \(\Sigma\) je konečná množina vstupních symbolů,
• \(D\) je konečná množina výstupních symbolů,
• \(\delta : Q \times \Sigma \to Q\) je přechodová funkce,
• \(\lambda : Q \to D\) je výstupní funkce (vázána na stav; parciální funkci zde nepřipouštíme),
• \(q_0 \in Q\) je počáteční stav.

Vztah Mealyho a Mooreova automatu

Každý Mealyho automat lze převést na Mooreův a obráceně. Platí, že pro vstup \(w \in \Sigma^*\) vyprodukuje Mealyho automat vždy výstup délky \(|w|\), zatímco Mooreův automat výstup délky \(|w| + 1\) (výstup začíná symbolem přiřazeným počátečnímu stavu).

Zásobníkový překladový automat

Definice (Zásobníkový překladový automat)

Zásobníkový překladový automat

(Nedeterministický) zásobníkový překladový automat (ZPA) je uspořádaná osmice \(ZPA = (Q, \Sigma, G, D, \delta, q_0, Z_0, F)\), kde:

• \(Q\) je konečná neprázdná množina stavů,
• \(\Sigma\) je konečná množina vstupních symbolů,
• \(G\) je konečná neprázdná množina zásobníkových symbolů,
• \(D\) je konečná množina výstupních symbolů,
• \(\delta\) je přechodová funkce definována jako zobrazení z \(Q \times (\Sigma \cup \{\varepsilon\}) \times G\) do množiny konečných podmnožin množiny \(Q \times G^* \times D^*\),
• \(q_0 \in Q\) je počáteční stav,
• \(Z_0 \in G\) je počáteční symbol na zásobníku,
• \(F \subseteq Q\) je množina koncových stavů.

Rozlišujeme ZPA přijímající přechodem do koncového stavu a ZPA přijímající s prázdným zásobníkem. Přechodovou funkci můžeme opět znázornit dvěma způsoby:

• Formální zápis:

  \[\delta(S, a, b) = \{(A, c, x)\}\]

  (ze stavu \(S\) na vstupní symbol \(a\) a symbol \(b\) na vrcholu zásobníku jdeme do stavu \(A\), na vrchol zásobníku vložíme symbol \(c\) (předtím odebereme \(b\)) a na výstup pošleme symbol \(x\))

• Stavový diagram:

  

Definice (Deterministický zásobníkový překladový automat)

Deterministický zásobníkový překladový automat

ZPA nazveme deterministickým, když má pro každý stav, symbol na vstupu a řetězec na zásobníku jasně dáno, jak pokračovat.

Zásobníkový překladový automat je deterministický, pokud je deterministický zásobníkový automat, který vznikne po vynechání výstupních symbolů.

Překlad definovaný zásobníkovým překladovým automatem

• Řetězce skládající se ze vstupních symbolů, které automat přijme, tvoří definiční obor.
• Naopak řetězce tvořící obor hodnot jsou složené z výstupních symbolů, které automat pošle na výstup při přijímání nějakého řetězce z definičního oboru.

Řetězec \(w\) z oboru hodnot je překladem řetězce \(x\) z definičního oboru právě tehdy, když automat přijme řetězec \(x\) a přitom na výstup pošle řetězec \(w\).