Ekvivalence konečných automatů a regulárních gramatik
V tomto dokumentu učiníme velmi důležitý závěr, který lze z předchozího vytušit. Regulární
jazyky jsme si definovali dvakrát, poprvé pomocí gramatik typu 3, neboli regulárních gramatik,
jejichž definici jsme uváděli v Chomského hierarchii gramatik. Podruhé jsme se o regulárních
jazycích bavili v souvislosti s konečnými automaty. Nyní je čas, abychom oba pojmy (regulární
gramatiky, konečné automaty) postavili na stejnou úroveň a prohlásili je za stejně „silné co se
týče množiny jazyků, které oba přijímají či generují.
Věta 1 (od regulární gramatiky ke konečnému automatu).
Ke každé regulární gramatice G = (N, Σ, P, S) existuje nedeterministický konečný automat
M = (Q, Σ, δ, q0, F) takový, že L(G) = L(M).
Důkaz (algoritmus pro převod).
Buď G = (N, Σ, P, S) regulární gramatika. Můžeme v ní mít pravidla tvaru A → a, A → aB,
kde A, B ∈ N, a ∈ Σ. Navíc zde může zde být pravidlo S → ε, ale potom S nesmí být na pravé
straně žádného pravidla.
Buď M = (Q, Σ, δ, q0, F) nedeterministický konečný automat s těmito vlastnostmi:
1. Q = {A, A ∈ N} ∪ {qf }, qf /∈ N;
2. F = {qf };
3. q0 = S;
4. δ je přechodová funkce, která vznikne takto:
a) máme-li pravidlo A → aB, pak B ∈ δ(A, a),
b) máme-li pravidlo A → a, pak qf ∈ δ(A, a),
c) máme-li pravidlo S → ε, pak F = F ∪ {q0}.
Důkaz korektnosti: nejdříve je potřeba ukázat platnost ekvivalence
S ⇒∗
a1 . . . akB ⇐⇒ B ∈ δ(S, a1 . . . ak),
kde a1, . . . , ak ∈ Σ (k ∈ N0), S, B ∈ N. Důkaz provedeme pomocí matematické indukce vzhledem
ke k:
• Báze: buď k = 0, což znamená, že a1 . . . ak = ε. Nutně tedy B = S. Z definice rozšířené
přechodové funkce víme, že v jejím bázovém kroku je pro každý stav q ∈ Q definován
přechod pod ε takto: δ(q, ε) = q. Nutně tedy musí platit i B ∈ δ(S, ε).
• Indukční krok: Nechť pro všechna slova w délky maximálně k ∈ N0 platí tvrzení
S ⇒∗
wB ⇐⇒ B ∈ δ(S, w).
• Indukční krok: uvažujme všechna slova wa, kde w ∈ Σ∗
, a ∈ Σ, |w| ≤ k. Předpokládejme,
že S ⇒∗
waB a ukažme platnost ekvivalence
S ⇒∗
waB ⇐⇒ B ∈ δ(S, wa).
Dle tvaru pravidel v regulární gramatice G musí platit:
S ⇒∗
wC ⇒ waB,
kde C ∈ N, pro který platí C → aB ∈ P. Dle indukčního předpokladu však
1
1. z derivace S ⇒∗
wC plyne C ∈ δ(S, w) (|w| ≤ k),
2. z derivace C ⇒ aB plyne B ∈ δ(C, a) (|a| = 1).
Pokud dáme dohromady předchozí dva výsledky C ∈ δ(S, w) a B ∈ δ(C, a), dostáváme
B ∈ δ(S, wa)
Nyní je již celkem snadné ukázat platnost x ∈ L(G) ⇔ x ∈ L(M).
1. Pro x = ε platí
ε ∈ L(G) ⇔ S → ε ∈ P ⇐⇒ S ∈ F ⇔ ε ∈ L(M).
2. Pro x = wa (w ∈ Σ∗
, a ∈ Σ) platí
wa ∈ L(G) ⇔ S ⇒∗
wB ⇒ wa ⇐⇒ B ∈ δ(S, w), qf ∈ δ(B, a) ⇔ qf ∈ δ(S, wa).
Poznámka 1.
Předchozí důkaz bychom mohli rozdělit do dvou částí.
1. Algoritmus pro převod, který počítá se třemi druhy pravidel v regulární gramatice. Tvar
A → aB zachytíme v konečném automatu tak, že doplníme B ∈ δ(A, a). Najdeme-li
pravidlo A → a, pak přidáme qf ∈ δ(A, a), kde qf je nový stav patřící zároveň do F.
A konečně, je-li v množině pravidel S → ε, potom upravíme množinu F tak, že do ní
přidáme stav S.
2. Důkaz korektnosti, jehož hlavní částí je důkaz ekvivalence
S ⇒∗
a1 . . . akB ⇐⇒ B ∈ δ(S, a1 . . . ak),
kde a1, . . . , ak ∈ Σ (k ∈ N0), S, B ∈ N.
Příklad 1.
Převeďte regulární gramatiku G na nedeterministický konečný automat M tak, aby L(G) =
L(M). Gramatika G = ({S, A, B, C, D}, {a, b, c, d}, P, S).
P = {S → aA | bB | ε,
A → bC | b,
B → dD | a,
C → aA | cD,
D → aC | bB}
Řešení. Nejprve si všimněte, že S → ε ∈ P. To znamená, že množina koncových stavů bude
obsahovat i stav qS příslušný neterminálu S. Nedeterministický automat
M = ({qS, qA, qB, qC, qD, qf }, {a, b, c, d}, δ, qS, {qS, qf })
má přechodovou funkci δ danou následující tabulkou:
2
δ a b c d
↔ qS {qA} {qB} – –
qA – {qC, qf } – –
qB {qf } – – {qD}
qC {qA} – {qD} –
qD {qC} {qB} – –
← qf – – – –
Věta 2 (od konečného automatu k regulární gramatice).
Buď M = (Q, Σ, δ, q0, F) konečný automat, pak existuje gramatika G = (N, Σ, P, S) taková, že
L(G) = L(M).
Důkaz (algoritmus převodu).
Předpokládejme, že M = (Q, Σ, δ, q0, F je nedeterministický konečný automat. Položme
N = {q | q ∈ Q} a definujme množinu pravidel P v těchto bodech:
1. je-li p ∈ δ(q, a), kde p, q ∈ Q, a ∈ Σ, pak q → ap přidáme do P. Pokud navíc p ∈ F, přidej
ještě pravidlo q → a.
2. V případě, že q0 /∈ F, položíme S = q0. V opačném případě (q0 ∈ F ⇒ ε ∈ L(M)) vytvoříme
nový startovní neterminál S, přidáme jej do množiny N a provedeme následující:
S → ε | α,
kde α je zástupný symbol pro všechny pravé strany q0-pravidel.
Výslednou gramatikou je G = (N, Σ, P, S), která je jistě regulární.
Důkaz korektnosti: se provede matematickou indukcí tvrzení:
δ(q0, w) ∩ F = ∅ ⇐⇒ S ⇒∗
w,
kde w = a1 . . . ak ∈ Σ∗
, a to vzhledem k délce slova w. Nebudeme jej uvádět, protože je obměnou
předchozího důkazu, akorát v obráceném pořadí.
Poznámka 2.
Bod 2. definice množiny pravidel P má své opodstatnění, ačkoliv se to na první pohled nezdá.
Pokud ε ∈ L(M), má být i ε ∈ L(G). Jestliže bychom ponechali startovním neterminálem q0
a přidali pravidlo q0 → ε, nemáme zaručeno, že se neterminál q0 nebude vyskytovat na pravé
straně žádného pravidla. To by však bylo porušení podmínky v Chomského hierarchii gramatik.
Z toho důvodu se přidává nový startovní neterminál S, který obsahuje stejná pravidla jako
q0, navíc však potřebné S → ε. Tento neterminál na pravé straně pravidel určitě nenalezneme,
protože byl nově vytvořen.
Příklad 2.
Buď dán nedeterministický konečný automat M = ({q0, q1, q2}, {a, b}, δ, q0, {q2}) s přechodovou
funkcí δ zadanou tabulkou:
3
δ a b
→ q0 {q1, q2} {q1}
q1 {q0, q2} {q2}
← q2 {q2} {q0}
Převeďte automat M na ekvivalentní regulární gramatiku G.
Řešení. První důležité zjištění je, že stav q0 není koncový, tudíž nemusíme přidávat nový
startovní neterminál do gramatiky G. Nejdříve aplikujeme bod 1. Všude tam, kde se na pravé
straně vyskytuje koncový stav q2, musíme navíc přidat i pravidlo pro samotný vstupní symbol.
Např. pro stav q0 a přechod pod symbolem a: do množiny P přidáme pravidla q0 → aq1 | aq2.
Navíc ještě přidáme pravidlo q0 → a z důvodu q2 ∈ δ(q0, a), q2 ∈ F. Stejně tak pro přechod z q0
pod b, výsledkem tedy bude
q0 → aq1 | aq2 | a | bq1
Podobně pro stavy q1, q2. Výsledkem bude regulární gramatika G = ({q0, q1, q2}, {a, b}, P, q0) s
množinou pravidel P:
q0 → aq1 | aq2 | a | bq1
q1 → aq0 | aq2 | a | bq2 | b
q2 → aq2 | a | bq0
Poznámka 3.
Je samozřejmě možné, abyste si neterminály vhodně přejmenovali a symbolům q0, q1, . . . přiřadili
velká písmena latinské abecedy tak, jak je zvykem.
4