Kleeneho věta
Američan Stephen Cole Kleene (1909-1994) je považován za jednoho ze zakladatelů teoretické
informatiky. Jako žák Alonzo Churche se potkával se svými vrstevníky, Alanem Turingem či
Emilem Postem. Objevil regulární výrazy a významně se zabýval teorií rekurze, přičemž symbol
iterace se v odborných textech často nazývá Kleeneho hvězda (Kleene’s Star).
Tento dokument vám ukáže významný poznatek teoretické informatiky, který byl nazván
„Kleeneho větou . Postaví totiž regulární výrazy a konečné automaty na stejnou výpočetní
úroveň. V materiálu se dočtete, jakým způsobem převést regulární výraz na konečný automat
a naopak. Nejdříve si uvedeme formulaci Kleeneho věty a poté zavedeme tzv. regulární přechodový
graf, s jehož pomocí tvrzení dokážeme.
Věta 1 (Kleeneho věta).
Libovolný jazyk je popsatelný regulárním výrazem, právě když je rozpoznatelný konečným au-
tomatem.
Definice – regulární přechodový graf
Regulární přechodový graf M je pětice (Q, Σ, δ, I, F), kde
• Q je neprázdná konečná množina stavů,
• Σ je vstupní abeceda,
• δ : Q × Q → RE(Σ) je parciální přechodová funkce,
• I ⊆ Q je množina počátečních stavů,
• F ⊆ Q je množina koncových stavů.
Poznámka 1.
1. Z definice přechodové funkce δ by mělo vyplývat, že návěštím hran mezi jednotlivými stavy
jsou regulární výrazy. To můžou být pouze vstupní symboly (jak je tomu u konečného
automatu), ale i složitější výrazy zahrnující operace sjednocení (+), zřetězení (.) a iterace
(*).
2. Pro každé dva stavy platí, že v jednom směru může vést pouze jedna hrana!
3. Další zajímavostí je možnost více než jednoho počátečního stavu!
4. Je možná poněkud matoucí, že přechodová funkce má jinak zavedený definiční obor a obor
hodnot. Vstupem pro δ je dvojice stavů, první složkou je stav, ze kterého hrana vychází,
druhou složkou stav, do kterého naopak vchází. Výsledkem funkce je regulární výraz, který
chápeme jako návěští hrany.
Příklad 1.
Na obrázku si můžete prohlédnout regulární přechodový graf M, který popisuje jazyk
L = {uvu | u ∈ {a, b}, v ∈ {a, b}∗
} ∪ {ε, a, b}
M = ({q0, q1, q2, q3, q4}, {a, b}, δ, {q0, q2}, {q0, q1, q3, q4}), kde δ je znázorněna pomocí stavového
diagramu:
1
q0 q1
a+b
q2 q3
a.(a+b)*.a
q4
b.(a+b)*.b
Přechodová fukce δ zapsána výčtem:
δ(q0, q1) = a + b
δ(q2, q3) = a.(a + b)∗
.a
δ(q2, q4) = b.(a + b)∗
.b
Definice – akceptování slova
Buď M = (Q, Σ, δ, I, F) regulární přechodový graf, w ∈ Σ∗
slovo. Řekneme, že slovo w je
akceptováno grafem M, právě když
• existuje posloupnost stavů q0, q1, . . . , qn, kde q0 ∈ I, qn ∈ F, n ∈ N,
• a δ(qi, qi+1) je definována pro každé 0 ≤ i < n,
taková, že
• w lze rozdělit na n částí w = w1 . . . wn tak, že
• wi ∈ δ(qi−1, qi) pro každé 0 < i ≤ n.
Slovo ε je akceptováno M, pokud I ∩ F = ∅.
Poznámka 2.
Předchozí definice se může zdát poněkud složitá. Zjednodušeně řečeno stačí najít posloupnost
stavů takových, že zřetězením jejich hran získáme regulární výraz, kterým může být slovo w
popsáno. Nesmíme opomenout, že prvním stavem zmíněné posloupnosti je počáteční, posledním
stavem koncový.
Věta 2 (převod regulárního přechodového grafu na NFA s ε-kroky).
Pro libovolný regulární přechodový graf M = (Q, Σ, δ, I, F) existuje ekvivalentní nedeterministický
konečný automat M′
s ε-kroky.
Poznámka 3.
Pokud ukážeme platnost této věty, jsme schopni převést i samotný regulární výraz E na odpovídající
konečný automat. Pokud totiž vytvoříme regulární přechodový graf o dvou stavech
q0 ∈ I, q1 ∈ F takový, že jediným jeho přechodem bude hrana z q0 do q1 s návěštím E, měli
bychom díky platnosti Věty 2 sestrojit ekvivalentní konečný automat.
2
Důkaz.
Zvolme nový počáteční stav q0 /∈ Q a položme Q′
= Q ∪ {q0}.Transformujme regulární přechodový
graf M pomocí následujících tří kroků:
1. Pro každý stav q ∈ I přidejme přechod δ′
(q0, q) = ε (napojení q0 na všechny původní
počáteční stavy z množiny I).
2. Vyberme libovolný přechod δ(p, q) = E původního regulárního přechodového grafu, kde
p, q ∈ Q a E ⊆ RE(Σ) takový, že E /∈ Σ∪{ε}. Nahradíme jej pomocí těchto čtyř pravidel:
2a. Je-li E = ∅, odstraníme přechod úplně.
2b. Je-li E = F + G, vložíme dva přechody δ(p, q) = F a δ(p, q) = G.
p q
F+G
p q
F
G
2c. Je-li E = F.G, vložíme do Q′
nový stav r /∈ Q a přidáme přechody δ(p, r) = F a
δ(r, q) = G.
p q
F.G
p r
F
q
G
2d. Je-li E = F∗
, vložíme do Q′
nový stav r /∈ Q a přidáme přechody δ(p, r) = ε,
δ(r, r) = F a δ(r, q) = ε.
p q
F*
p r q
εε
F
3. Kroky 2a až 2d opakujeme do té doby, než některá z hran má návěští různé od Σ ∪ {ε}.
Výsledný regulární přechodový graf je stavovým diagramem ekvivalentního NFA M′
= (Q′
, Σ, δ′
, q0, F)
s ε-kroky, jehož přechodová funkce δ′
je modifikací výsledné funkce δ:
Jestliže δ(p, q) obsahuje x ∈ Σ ∪ {ε}, přidáme {q} ∈ δ′
(p, x).
Poznámka 4.
Důkaz Věty 2 je konstruktivní v tom smyslu, že je zároveň algoritmem pro převod. Je však
zároveň korektní, protože je postaven na transformaci dle kroků 2a až 2d, které jistě zachovávají
ekvivalenci jazyka vstupního i výstupního regulárního přechodového grafu.
Příklad 2.
Je dán regulární výraz E = (a.b)∗
.(a.a + b.b).(a + a.b)∗
. Sestrojte konečný automat M tak, aby
L(M) = L(E).
3
Řešení. Začínáme tím, že vytvoříme regulární přechodový graf M = ({q0, q1}, {a, b}, δ, {q0}, {q1},
jehož jediným přechodem bude δ(q0, q1) = E.
q0 q1
(a.b)*.(a.a+b.b).(a+a.b)*
Nyní je potřeba, abyste si všimli, že výraz E je zřetězením tří podvýrazů. Dle kroku 2c tedy
vložíme dva nové stavy r, s a přechody δ(q0, r) = (a.b)∗
, δ(r, s) = (a.a+b.b), δ(s, q1) = (a+a.b)∗
:
q0 r s q1
(a.b)* a.a+b.b (a+a.b)*
Vznikly tři hrany, které ještě musíme dále transformovat. V prvním a třetím případě se jedná
o iterace, použijeme tedy krok 2d a vložíme dva nové stavy t, u, abychom mohli nahradit
δ(q0, r) = (a.b)∗
za přechody δ(q0, t) = ε, δ(t, t) = a.b, δ(t, r) = ε
δ(s, q1) = (a.a + b)∗
za přechody δ(s, u) = ε, δ(u, u) = a.a + b, δ(u, q1) = ε
Přechod ze stavu r do stavu s znásobíme (dle bodu 2b), tj. přidáme dvě paralelní hrany
δ(r, s) = a.a, δ(r, s) = b.b
q0 r s q1
a.b
a.a
t
ε ε
b.b
a+a.b
u
ε ε
Nyní nám zbývají převést 4 jednoduché hrany:
1. smyčku u stavu t odstraníme tak, že přidáme nový stav v a přechody δ(t, v) = a, δ(v, t) = b
(viz bod 2c).
2. přechod δ(r, s) = aa nahradíme za dva přechody jdoucí přes nový stav w (bod 2c):
δ(r, w) = a, δ(w, s) = a.
3. Stejným způsobem jako v předchozím případě, tj. vytvoříme nový stav x, který bude
„mostem pro stavy r, s: δ(r, x) = b, δ(x, s) = b.
4. V případě smyčky a+a.b nad stavem u si dovolíme dva kroky najednou. Nejdříve zajistíme
smyčku pod a (δ(u, u) = a), následně vytvoříme nový stav y a přechody
δ(u, y) = a, δ(y, u) = b.
4
Výsledkem je stavový diagram automatu M′
, který přijímá stejný jazyk, jaký popisuje výraz
E = (a.b)∗
.(a.a + b.b).(a + a.b)∗
.
q0 r s q1
a
t
ε ε
b
a
u
ε ε
w
a
x
b
v
ba
y
a
b
Věta 3 (převod DFA na regulární přechodový graf).
Pro každý regulární přechodový graf M = (Q, Σ, δ, I, F) existuje ekvivalentní regulární přechodový
graf M′
= ({x, y}, Σ, δ′
, {x}, {y}), kde δ′
je definováno pouze pro dvojici (x, y).
Poznámka 5.
Algoritmus popsaný v důkazu Věty 3 můžeme použít pro převod deterministického konečného
automatu M na dvoustavový regulární přechodový graf, jehož jediná hrana je popsána regulárním
výrazem E takovým, že L(E) = L(M). To znamená, že díky tomu dokážeme zapsat
regulární výraz popisující jazyk L(M) konečného automatu M.
Důkaz.
Transformace regulárního přechodového grafu M na ekvivalentní M′
o dvou stavech x, y probíhá
ve čtyřech následujících krocích:
1. nejdříve vložíme dva nové stavy x, y /∈ Q a přidáme hrany δ(x, p) = ε (pro každý p ∈ I) a
δ(q, y) = ε (pro každý q ∈ F). Stav p bude počáteční stav M′
, stav y naopak koncový.
2. Každý stav q ∈ Q (různý od x, y) postupně odstraníme podle následující myšlenky: uvažujme
libovolné dva stavy r, s, pro které platí, že
• z r vychází hrana s návěštím F ∈ RE(Σ) do q,
• z q vychází hrana s návěštím G ∈ RE(Σ) do s.
5
• Navíc pro stav q může nastat i situace, že δ obsahuje přechody δ(q, q) = E1, δ(q, q) =
E2, . . . , δ(q, q) = En (n ∈ N), tj. δ(q, q) = E1 + E2 + · · · + En.
Stav q můžeme odstranit, pokud pro každou takovou dvojici (r, s) vytvoříme hranu s
návěštím F.(E1 + E2 + · · · + En + ∅)∗
.G.
3. Pokud nalezneme stav p takový, že do něj žádná hrana nevchází, nebo naopak žádná hrana
z něj nevychází, pak se jedná o nedosažitelný stav, resp. o stav, z něhož nikdy nemůžeme
dosáhnout koncového stavu. Stav p tedy můžeme odstranit i spolu s hranami, které do něj
buď vchází nebo vychází, a jazyk L(M′
) se nezmění.
4. Kroky 2, 3 provádíme do té doby, než v regulárním přechodovém grafu zůstanou pouze
stavy x, y a konečný počet hran z x do y. Pomocí operátoru + můžeme spojit jejich návěští
a máme návěští jediné hrany mezi x, y.
Příklad 3.
2. krok algoritmu si raději ještě znázorníme na příkladu jednoduchého přechodového grafu M o
pěti stavech p, q, r, s, x, přičemž bychom rádi odstranili stav x.
p
x
r
F H
q s
G I
E
Je zapotřebí si všimnout, že přes stav x vedou 4 možné cesty, které můžeme znázornit pomocí
těchto regulárních výrazů:
1. ze stavu p do r: δ(p, r) = F.(E + ∅)∗
.H,
2. ze stavu p do s: δ(p, s) = F.(E + ∅)∗
.I,
3. ze stavu q do r: δ(q, r) = G.(E + ∅)∗
.H,
4. ze stavu q do s: δ(q, s) = G.(E + ∅)∗
.I.
Odstraněním stavu x tedy vznikne tento regulární přechodový graf (0 značíme ∅):
p r
q s
F.(E+0)*.H
F.(E+0)*.I
G.(E+0)*.I
G.(E+0)*.H
6
Příklad 4.
Je dán následující konečný automat M = ({p, q, r, s, t}, {a, b, c}, δ, p, {r, t}), kde přechodová
funkce je znázorněna pomocí stavového diagramu:
p q r
ts
c
cc
a, b a
a
ab
Nalezněte odpovídající regulární výraz E tak, aby platilo L(M) = L(E).
Řešení. Nejdříve přidáme stavy x, y, přičemž x bude počáteční stav, y koncový. Je nutno též
doplnit hrany
δ(x, p) = ε,
δ(r, y) = ε,
δ(t, y) = ε.
Odstranění stavu p
Začneme po pořádku, tj. chceme odstranit stav p. Do něj vede ε-hrana z x a vychází z něj hrana
a + b do stavu q. Stačí tedy přidat přechod
δ(x, q) = ε.(a + b) = a + b
Odstranění stavu q
Stavu q se týkají dvě cesty:
1. cesta x − q − r a přechody δ(x, q) = a + b, δ(q, r) = a.
2. cesta s − q − r a přechody δ(s, q) = b, δ(q, r) = a.
3. cesta q − q a přechod δ(q, q) = c.
Stav q odstraníme a doplníme o následující dva přechody nahrazující cesty v bodech 1, 2:
δ(x, r) = (a + b).(c + ∅)∗
.a, δ(s, r) = b.(c + ∅)∗
.a
Raději si mezivýsledek znovu zobrazíme, abychom lépe rozhodli, jak pokračovat dále.
7
x r
ts
cc
(a+b).(c+0)*.a
a
ab.(c+0)*.a
y
ε
ε
Odstranění stavu t
Asi uznáte, že nejvýhodnější bude teď odstranění stavu t. Přes něj vede pouze jediná cesta
s − t − y. Můžeme jej tedy odstranit a přidat přechod
δ(s, y) = a.(c + ∅)∗
.ε
Odstranění stavu s
Odstranění stavu s není triviální. Nejdříve si napišme, jaké cesty vedou přes s:
1. cesta r − s − r a přechody δ(r, s) = a, δ(s, r) = b.(c + ∅)∗
.a.
2. Cesta r − s − y a přechody δ(r, s) = a, δ(s, y) = a.(c + ∅)∗
.ε = a.(c + ∅)∗
.
3. A nakonec i smyčka v podobě přechodu δ(s, s) = c.
Stav s můžeme odstranit, přidáme přechody, které nahrazují cesty v bodech 1, 2. Všimněte si
přechodu r do y, kde jsme ještě museli zahrnout i existující přechod pod ε:
δ(r, r) = a.(c + ∅)∗
.b.(c + ∅)∗
.a, δ(r, y) = ε + (a.(c + ∅)∗
.a.(c + ∅)∗
)
Opět si raději mezivýsledek zobrazíme pomocí obrázku:
x r
(a+b).(c+0)*.a
y
ε+(a. )(c+0)*.a.(c+0)*
a.(c+0)*.b.(c+0)*.a
Odstranění stavu r
To už je víceméně triviální, všechny tři přechody
1. F = δ(x, r) = (a + b).(c + ∅)∗
.a,
2. G = δ(r, r) = a.(c + ∅)∗
.b.(c + ∅)∗
.a,
3. H = δ(r, y) = ε + (a.(c + ∅)∗
.a.(c + ∅)∗
)
8
spojíme dohromady a máme výsledek:
E = F.(G + ∅)∗
.H
= [(a + b).(c + ∅)∗
.a].[∅ + a.(c + ∅)∗
.b.(c + ∅)∗
.a]∗
.[ε + (a.(c + ∅)∗
.a.(c + ∅)∗
)]
Přitom platí, že L(M) = L(E).
9