Formální jazyky a automaty
Věta o vkládání, Myhillova-Nerodova věta
Jan Křetínský
Fakulta informatiky, MU Brno
Jaro 2024
Omezená vyjadřovací síla konečných automatů
L = {an
bn
| n ≥ 0} = {ε, ab, aabb, aaabbb, aaaabbbb . . .}
a a a a a b b b b b
2 / 20
an
bn
není regulární
Předpokládejme, že existuje automat M příjímající jazyk L.
Nechť M má k stavů.
Uvažme výpočet M na slově an
bn
kde n > k.
aaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbb
Protože n > k, musí existovat (z Dirichletova principu) stav p takový,
že při čtení iniciální posloupnosti symbolů a projde automat stavem p
(alespoň) dvakrát.
3 / 20
an
bn
není regulární
Předpokládejme, že existuje automat M příjímající jazyk L.
Nechť M má k stavů.
Uvažme výpočet M na slově an
bn
kde n > k.
x y z
aaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbb
↑ ↑ ↑ ↑
q0 p p r ∈ F
Protože n > k, musí existovat (z Dirichletova principu) stav p takový,
že při čtení iniciální posloupnosti symbolů a projde automat stavem p
(alespoň) dvakrát.
Proto xyz ∈ L =⇒
xz ∈ L
xyyz ∈ L
3 / 20
an
bn
není regulární – formálně
Platí ˆδ(q0, x) = p ˆδ(p, y) = p ˆδ(p, z) = r ∈ F
Pak ale i ˆδ(q0, xz) = ˆδ(ˆδ(q0, x), z) = ˆδ(p, z) = r ∈ F
Analogicky můžeme y i (vícekrát) „vsunout“:
ˆδ(q0, xyyz) = ˆδ(ˆδ(ˆδ(ˆδ(q0, x), y), y), z)
= ˆδ(ˆδ(ˆδ(p, y), y), z)
= ˆδ(ˆδ(p, y), z)
= ˆδ(p, z)
= r ∈ F
4 / 20
Pumping lemma: Obecná formalizace
Lemma [o vkládání / pumping lemma]
Nechť L je regulární jazyk.
Pak existuje n ∈ N takové, že libovolné slovo w ∈ L délky alespoň n
lze psát ve tvaru w = xyz, kde |xy| ≤ n, y ̸= ε a xyi
z ∈ L pro každé
i ∈ N0.
Důkaz. Nechť DFA M = (Q, Σ, δ, q0, F) rozpoznává jazyk L.
Položme n = card(Q).
Pro libovolné slovo w ∈ L délky alespoň n platí, že automat M
projde při akceptování slova w (alespoň) dvakrát stejným stavem.
Slovo w tedy můžeme rozdělit na tři části: w = xyz, kde y ̸= ε a
ˆδ(q0, x) = p, ˆδ(p, y) = p a ˆδ(p, z) = r ∈ F. Je zřejmé, že ke zopakování
nějakého stavu dojde nejpozději po zpracování prvních n znaků a tedy
lze klást |xy| ≤ n.
Dále ˆδ(p, yi
) = p pro libovolné i ∈ N0, proto také ˆδ(q0, xyi
z) = r,
tj. xyi
z ∈ L(M) pro každé i ∈ N0.
5 / 20
Pumping lemma: Použití
Pumping lemma
L je regulární =⇒ ∃n ∈ N .
∀w ∈ L . |w| ≥ n =⇒
∃x, y, z . ( w = xyz ∧ y ̸= ε ∧ |xy| ≤ n ∧
∀i ≥ 0 . xyi
z ∈ L )
Pomocí pumping lemmatu lze dokázat, že nějaký jazyk není regulární:
Nechť pro jazyk L platí:
pro libovolné n ∈ N
existuje takové slovo w ∈ L délky alespoň n, pro které platí, že
při libovolném rozdělení slova w na takové tři části x, y, z,
že |xy| ≤ n a y ̸= ε,
existuje alespoň jedno i ∈ N0 takové, že xyi
z ̸∈ L.
Pak L není regulární.
6 / 20
Myhillova-Nerodova věta: Motivace I
Algebraický popis automatu: DFA → ∼
Každý DFA (Q, Σ, δ, q0, F) s totální přechodovou funkcí definuje
ekvivalenci ∼ na Σ∗
:
u ∼ v
def
⇐⇒ ˆδ(q0, u) = ˆδ(q0, v)
Příklad: L = {w ∈ {a, b}∗
| #a(w) ≥ 2}
7 / 20
Pravá kongruence
Definice 2.20.
Nechť Σ je abeceda a ∼ je ekvivalence na Σ∗
. Ekvivalence ∼ je pravá
(zprava invariantní) kongruence, pokud pro každé u, v, w ∈ Σ∗
platí:
u ∼ v =⇒ uw ∼ vw
Ekvivalentně (Tvrzení 2.21. ):
. . . pro každé u, v ∈ Σ∗
, a ∈ Σ platí u ∼ v =⇒ ua ∼ va.
(Implikace =⇒ je triviální, implikace ⇐= se snadno ukáže indukcí
k délce zprava přiřetězeného slova w.)
Index ekvivalence ∼ je počet tříd rozkladu Σ∗
/∼.
Je-li těchto tříd nekonečně mnoho, klademe index ∼ roven ∞.
8 / 20
Příklady
Jsou tyto relace na slovech nad abecedou Σ = {a, b} pravé
kongruence?
1 u ∼ v ⇐⇒ u a v začínají stejným symbolem nebo u = v = ε
index ∼ je . . .
2 u ∼ v ⇐⇒ #a(u) = #a(v)
index ∼ je . . .
3 u ∼ v ⇐⇒ u a v mají stejné předposlední písmeno nebo
|u|, |v| ≤ 1
index ∼ je . . .
9 / 20
Myhillova-Nerodova věta: Motivace II
A naopak: ∼ → DFA
Pravá kongruence ∼ na Σ∗
s konečným indexem jednoznačně (až na
pojmenování stavů) určuje DFA (Q, Σ, δ, q0, ∅) s totální přechodovu
funkcí a bez nedosažitelných stavů slpňující:
ˆδ(q0, u) = ˆδ(q0, v) ⇐⇒ u ∼ v
Příklad: u ∼ v ⇐⇒ u a v začínají stejným symbolem nebo u = v = ε
10 / 20
Prefixová ekvivalence
Definice 2.25.
Nechť L je libovolný (ne nutně regulární) jazyk nad abecedou Σ. Na
množině Σ∗
definujeme relaci ∼L zvanou prefixová ekvivalence pro L
takto:
u ∼L v
def
⇐⇒ ∀w ∈ Σ∗
: uw ∈ L ⇐⇒ vw ∈ L
Věta.
∼L je pravá kongruence.
11 / 20
Příklady
1 L = {w ∈ {a, b}∗
| #a(w) ≥ 2}
index ∼L je . . .
2 L = {an
bn
| n ≥ 0}
index ∼L je . . .
12 / 20
Myhillova-Nerodova věta: Formalizace
Věta 2.28. (Myhill-Nerode, 1957)
Nechť L je jazyk nad Σ. Pak tato tvrzení jsou ekvivalentní:
1 L je rozpoznatelný deterministickým konečným automatem.
2 L je sjednocením některých tříd rozkladu určeného pravou
kongruencí na Σ∗
s konečným indexem.
3 Relace ∼L má konečný index.
Důkaz.
1 =⇒ 2
2 =⇒ 3
3 =⇒ 1
13 / 20
Myhillova-Nerodova věta: Důkaz 1 =⇒ 2
Jestliže L je rozpoznatelný deterministickým konečným automatem
pak L je sjednocením některých tříd rozkladu určeného pravou
kongruencí na Σ∗
s konečným indexem.
pro daný L rozpoznáváný automatem M zkonstruujeme relaci
požadovaných vlastností
M = (Q, Σ, δ, q0, F), δ je totální
na Σ∗
definujme binární relaci ∼ předpisem
u ∼ v
def
⇐⇒ ˆδ(q0, u) = ˆδ(q0, v)
ukážeme, že ∼ má požadované vlastnosti
14 / 20
u ∼ v
def
⇐⇒ ˆδ(q0, u) = ˆδ(q0, v)
∼ je ekvivalence (je reflexivní, symetrická, tranzitivní)
∼ má konečný index
třídy rozkladu odpovídají stavům automatu
∼ je pravá kongruence:
Nechť u ∼ v a a ∈ Σ. Pak
ˆδ(q0, ua) = δ(ˆδ(q0, u), a) = δ(ˆδ(q0, v), a) = ˆδ(q0, va) a tedy
ua ∼ va.
L je sjednocením těch tříd rozkladu určeného relací ∼, které
odpovídají koncovým stavům automatu M
15 / 20
Myhillova-Nerodova věta: Důkaz 2 =⇒ 3
Nechť L je sjednocením některých tříd rozkladu určeného pravou
kongruencí ∼ na Σ∗
s konečným indexem.
Pak prefixová ekvivalence ∼L má konečný index.
u ∼ v =⇒ u ∼L v pro všechna u, v ∈ Σ∗
(tj. ∼⊆∼L) [Lemma 2.27]
každá třída ekvivalence relace ∼ je celá obsažena v nějaké třídě
ekvivalence ∼L
index ekvivalence ∼L je menší nebo roven indexu ekvivalence ∼
∼ má konečný index =⇒ ∼L má konečný index
16 / 20
Myhillova-Nerodova věta: Důkaz 3 =⇒ 1
Nechť prefixová ekvivalence ∼L má konečný index.
Pak jazyk L je rozpoznatelný deterministickým konečným automatem.
Zkonstruujeme automat M = (Q, Σ, δ, q0, F) přijímající L:
Q = Σ∗
/∼L
Stavy jsou třídy rozkladu Σ∗
určeného ekvivalencí ∼L.
Je jich tedy konečně mnoho.
q0 = [ε]
δ je definována pomocí reprezentantů: δ([u], a) = [ua]
Definice δ je korektní, protože nezávisí na volbě reprezentanta.
F = {[v] | v ∈ L}
Důkaz korektnosti, tj. L = L(M)
ˆδ([ε], v) = [v] pro každé v ∈ Σ∗
(indukcí k délce slova v)
v ∈ L(M) ⇐⇒ ˆδ([ε], v) ∈ F ⇐⇒ [v] ∈ F ⇐⇒ v ∈ L
17 / 20
Myhill-Nerodova věta: Použití 1/3
Větu lze použít k důkazu neregularity jazyka, např.
L = {ai
b j
| i, j ≥ 0, i ̸= j}
Nechť i ̸= j. Pak ai
̸∼L aj
, protože ai
b j
∈ L ale aj
b j
̸∈ L.
Žádné dvě ze slov a1
, a2
, a3
, a4
, a5
, a6
, . . . nepadnou do stejné třídy
ekvivalence relace ∼L.
∼L nemá konečný index =⇒ L není regulární (¬3 =⇒ ¬1)
18 / 20
Myhill-Nerodova věta: Použití 2/3
Větu lze použít i k důkazu regularity jazyka, např.
L = {w ∈ {a, b}∗
| #a(w) ≥ 2}
Třídy ekvivalence relace ∼L: T1 = {w ∈ {a, b}∗
| #a(w) = 0}
T2 = {w ∈ {a, b}∗
| #a(w) = 1}
T3 = {w ∈ {a, b}∗
| #a(w) ≥ 2}
∼L má konečný index =⇒ L je rozpoznatelný deterministickým
konečným automatem, tj. regulární (3 =⇒ 1)
19 / 20
Myhill-Nerodova věta: Použití 3/3
Minimalizace DFA
Věta 2.29. a 2.31.
Minimální deterministický konečný automat s totální přechodovou
funkcí akceptující jazyk L je určen jednoznačně až na isomorfismus (tj.
přejmenování stavů). Počet stavů tohoto automatu je roven indexu
prefixové ekvivalence ∼L.
20 / 20
Myhill-Nerodova věta: Použití 3/3
Minimalizace DFA
Věta 2.29. a 2.31.
Minimální deterministický konečný automat s totální přechodovou
funkcí akceptující jazyk L je určen jednoznačně až na isomorfismus (tj.
přejmenování stavů). Počet stavů tohoto automatu je roven indexu
prefixové ekvivalence ∼L.
Učení DFA
20 / 20