Na obrázku níže je znázorněn minimální automat pro L, spolu s příslušnými třídami rozkladu Σ∗
/∼L =
{T1, T2}.
1
2
T1 = {w ∈ Σ∗
| w má sudou délku}
T2 = {w ∈ Σ∗
| w má lichou délku}
a, ba, b
Zadání po nás chce pravou kongruenci ∼, která vznikne z ∼L rozdělením některé třídy rozkladu na dvě.
Na minimálním automatu to odpovídá zdvojení některého stavu tak, že oba „dvojníci budou dosažitelní.
Do prvního stavu vedou 3 hrany, takže máme 3 možnosti (kterákoli hrana může zůstat samotná):
1
2
3
T1 = {ε}
T2 = {w ∈ Σ∗
| w má lichou délku}
T3 = {w ∈ Σ∗
| w má kladnou sudou délku}a, b
a, b
a, b
1
2
3
T1 = {ε} ∪ {w ∈ Σ∗
| w má kladnou sudou délku a končí béčkem}
T2 = {w ∈ Σ∗
| w má lichou délku}
T3 = {w ∈ Σ∗
| w má kladnou sudou délku a končí áčkem}a, b
ab
a, b
1
2
3
T1 = {ε} ∪ {w ∈ Σ∗
| w má kladnou sudou délku a končí áčkem}
T2 = {w ∈ Σ∗
| w má lichou délku}
T3 = {w ∈ Σ∗
| w má kladnou sudou délku a končí béčkem}a, b
ba
a, b
Do druhého stavu vedou 2 hrany, takže jedinou možností je rozdělit je „1 + 1 .
1
2 3
T1 = {w ∈ Σ∗
| w má sudou délku}
T2 = {w ∈ Σ∗
| w má lichou délku a končí áčkem}
T3 = {w ∈ Σ∗
| w má lichou délku a končí béčkem}
a b
a, b a, b
Pro odpovídající pravé kongruence ∼, určené rozkladem Σ∗
/∼ = {T1, T2, T3}, v prvních dvou případech
platí a2
ε (řešení a)), ve zbylých případech platí a2
∼ ε (řešení b)). Všechny 4 splňují a2
∼ a4
,
takže pro úlohu c) žádná vyhovující pravá kongruence ∼ neexistuje; důkaz je následující:
Předpokládejme pro spor, že existuje vyhovující ∼. Jelikož index(∼) = 3, musí některá dvě ze slov
a, a2
, a3
, a4
být ekvivalentní dle ∼, ovšem všechny možnosti přivedeme ke sporu:
• ai
∼ aj
pro i, j různé parity je ve sporu s požadavkem, že L je sjednocením tříd rozkladu Σ∗
/∼,
neboť zřejmě právě jedno z dotyčných slov leží v L.
• a2
∼ a4
je přímo vyloučeno zadáním;
• a ∼ a3
implikuje (přiřetězením a zprava) a2
∼ a4
, spor.
2