2.2.7 Skládání konečných automatů
Skládání automatů nám umožňuje konstruovat automaty pro složitější jazyky pomocí jednodušších automatů a operací nad jazyky.
Operace a konstrukce
Sjednocení
Pro dva KA \(M_1\) a \(M_2\) zkonstruujeme KA přijímající sjednocení jazyků \(L(M_1) \cup L(M_2)\) následovně:
- pomocí \(\varepsilon\)-přechodů: Vytvoříme nový počáteční stav a \(\varepsilon\)-přechody do původních počátečních stavů (vstupní \(M_1\) a \(M_2\) jsou NKA, NKA s \(\varepsilon\)-přechody nebo DKA).
- jako NKA s více počátečními stavy: Sjednotíme množiny počátečních stavů (vstupní \(M_1\) a \(M_2\) jsou NKA, NKA s \(\varepsilon\)-přechody nebo DKA).
- pomocí paralelní činnosti: Vstupní \(M_1\) a \(M_2\) musí být úplně určené DKA nebo úplně určené NKA. Stavy výsledného automatu jsou dvojice \((q_1, q_2)\), kde \(q_1\) je stav z \(M_1\) a \(q_2\) z \(M_2\). Koncové stavy jsou ty, které obsahují koncový stav alespoň jednoho ze vstupních automatů.
Průnik
Pro dva KA \(M_1\) a \(M_2\) zkonstruujeme KA přijímající průnik jazyků \(L(M_1) \cap L(M_2)\) pomocí paralelní činnosti.
- Vstupní \(M_1\) a \(M_2\) jsou NKA (bez \(\varepsilon\)-přechodů a s jedním počátečním stavem) či DKA, nemusí být úplně určené.
- Koncové stavy výsledného automatu jsou ty dvojice, které obsahují koncový stav z obou vstupních automatů zároveň.
Konstrukce pomocí paralelní činnosti
Paralelní činnost (Produktová konstrukce)
Tento algoritmus se používá pro sjednocení a průnik. Předpokládáme dva automaty \(M_1 = (Q_1, \Sigma, \delta_1, q_{01}, F_1)\) a \(M_2 = (Q_2, \Sigma, \delta_2, q_{02}, F_2)\), které jsou úplně určené (DKA nebo NKA). Výsledný automat \(M = (Q, \Sigma, \delta, q_0, F)\) pracuje následovně:
- Stavy (\(Q\)): Stavy jsou uspořádané dvojice ze součinu množin stavů původních automatů. \(Q = Q_1 \times Q_2\)
- Počáteční stav (\(q_0\)): Dvojice tvořená počátečními stavy obou automatů. \(q_0 = (q_{01}, q_{02})\)
- Přechodová funkce (\(\delta\)): Přechody jsou definovány po složkách. Automat simuluje oba automaty zároveň. Pro \(p \in Q_1, q \in Q_2, a \in \Sigma\): \(\delta((p, q), a) = (\delta_1(p, a), \delta_2(q, a))\)
- Koncové stavy (\(F\)): Liší se podle operace:
- Pro sjednocení (\(L_1 \cup L_2\)): Alespoň jeden stav ve dvojici musí být koncový. \(F = (F_1 \times Q_2) \cup (Q_1 \times F_2)\)
- Pro průnik (\(L_1 \cap L_2\)): Oba stavy ve dvojici musí být koncové. \(F = F_1 \times F_2\)
Doplněk jazyka
Pro KA \(M_1\) zkonstruujeme KA přijímající doplněk jazyka \(\overline{L(M_1)}\) pomocí prohození koncových a nekoncových stavů.
- Podmínka: Vstupní automat \(M_1\) musí být úplně určený DKA.
Rozdíl
Pro dva KA \(M_1\) a \(M_2\) zkonstruujeme KA přijímající rozdíl jazyků \(L(M_1) \setminus L(M_2)\) s využitím vztahu:
Součin (zřetězení)
Pro dva KA \(M_1\) a \(M_2\) zkonstruujeme KA přijímající součin jazyků \(L(M_1) \cdot L(M_2)\) pomocí \(\varepsilon\)-přechodů.
- Ze všech koncových stavů automatu \(M_1\) vedeme \(\varepsilon\)-přechody do počátečního stavu automatu \(M_2\).
- Koncové stavy automatu \(M_1\) přestanou být koncové (pokud \(\varepsilon \notin L(M_2)\)).
- Vstupní \(M_1\) a \(M_2\) jsou NKA, NKA s \(\varepsilon\)-přechody nebo DKA, nemusí být úplně určené.
Iterace
Pro KA \(M_1\) zkonstruujeme KA přijímající iteraci jazyka \(L(M_1)^*\) zavedením nového počátečního stavu a \(\varepsilon\)-přechodů.
- Přidáme nový počáteční stav, který je zároveň koncový (pro přijetí \(\varepsilon\)).
- Z nového počátečního stavu vedeme \(\varepsilon\)-přechod do původního počátečního stavu.
- Ze všech původních koncových stavů vedeme \(\varepsilon\)-přechody zpět do původního počátečního stavu.
- Vstupní \(M_1\) je NKA, NKA s \(\varepsilon\)-přechody nebo DKA, nemusí být úplně určený.
Důležitost nového počátečního stavu u iterace
U iterace je nutné přidat nový počáteční stav. Nelze pouze prohlásit původní počáteční stav za koncový, protože by to mohlo změnit jazyk nesprávným způsobem (např. přijetím slov, která v iteraci být nemají, pokud se do počátečního stavu vrací nějaký cyklus).
Algoritmy pro rozhodování vlastností
Rozhodnutí, zdali \(L(M) = \Sigma^*\)
- Pro automat \(M\) vytvoříme ekvivalentní deterministický minimální automat \(M'\).
- Pokud má automat \(M'\) pouze jeden stav, který je zároveň počáteční a koncový se smyčkou pro všechny symboly \(a \in \Sigma\), poté \(L(M) = \Sigma^*\), jinak \(L(M) \neq \Sigma^*\).
Rozhodnutí, zdali \(L(M) = \emptyset\)
- Pro automat \(M\) vytvoříme ekvivalentní automat \(M'\) bez nedosažitelných stavů.
- Pokud v automatu \(M'\) neexistují žádné koncové stavy, poté \(L(M) = \emptyset\), jinak \(L(M) \neq \emptyset\).
Rozhodnutí, zdali L(M1) = L(M2)
Rozhodnutí, zdali \(L(M_1) = L(M_2)\)
- Pro automat \(M_1\) vytvoříme ekvivalentní deterministický minimální automat \(M'_1\).
- Pro automat \(M_2\) vytvoříme ekvivalentní deterministický minimální automat \(M'_2\).
- Pokud mezi automaty \(M'_1\) a \(M'_2\) existuje izomorfismus, poté \(L(M_1) = L(M_2)\), jinak \(L(M_1) \neq L(M_2)\).
Rozhodnutí, zdali L(M1) ⊆ L(M2)
Rozhodnutí, zdali \(L(M_1) \subseteq L(M_2)\)
Využijeme vztahu \(L(M_1) \subseteq L(M_2) \iff L(M_1) \setminus L(M_2) = \emptyset\).
- Vytvoříme automat \(M_3\) přijímající jazyk \(L(M_3) = L(M_1) \cap \overline{L(M_2)}\).
- Rozhodneme, zda \(L(M_3) = \emptyset\) (viz algoritmus výše).
- Pokud \(L(M_3) = \emptyset\), pak platí \(L(M_1) \subseteq L(M_2)\).