Formální jazyky a automaty
Uzávěrové vlastnosti regulárních jazyků, regulární výrazy
Jan Křetínský
Fakulta informatiky, MU Brno
Jaro 2024
Uzávěrové vlastnosti regulárních jazyků
Věta 2.49. a 2.51.
Třída regulárních jazyků je uzavřená na sjednocení, průnik, rozdíl a
komplement.
Důkaz. synchronní paralelní kompozice automatů + komplement.
2 / 29
Uzávěrové vlastnosti regulárních jazyků
Věta 2.49. a 2.51.
Třída regulárních jazyků je uzavřená na sjednocení, průnik, rozdíl a
komplement.
Důkaz. synchronní paralelní kompozice automatů + komplement.
Aplikace: (I)regularita
2 / 29
Uzávěrové vlastnosti regulárních jazyků
Věta 2.49. a 2.51.
Třída regulárních jazyků je uzavřená na sjednocení, průnik, rozdíl a
komplement.
Důkaz. synchronní paralelní kompozice automatů + komplement.
Aplikace: (I)regularita
Příklad:
L1 = {ai
bi
cj
| 2i ≥ j ≥ 0}
L2 = {a}∗
.{b}∗
L3 = {an
bn
| n ≥ 0}
L1 ∩ L2 = L3
Jazyk L2 je regulární, L3 není regulární =⇒ L1 není regulární.
2 / 29
Jednodušší konstrukce pro sjednocení
M2
M1
Jednodušší konstrukce pro sjednocení
M2
M1
ε
ε
3 / 29
Jednodušší konstrukce pro sjednocení
M2
M1
ε
ε
3 / 29
Uzavřenost na zřetězení
Věta 2.52.
Třída regulárních jazyků je uzavřená na zřetězení.
Důkaz:
4 / 29
Uzavřenost na zřetězení
Věta 2.52.
Třída regulárních jazyků je uzavřená na zřetězení.
Důkaz:
M1 M2
Nechť L1 a L2 jsou regulární jazyky, rozpoznávané NFA
M1 = (Q1, Σ1, δ1, q1, F1) a M2 = (Q2, Σ2, δ2, q2, F2), kde Q1 ∩ Q2 = ∅.
Uzavřenost na zřetězení
Věta 2.52.
Třída regulárních jazyků je uzavřená na zřetězení.
Důkaz:
M1 M2
ε
ε
Nechť L1 a L2 jsou regulární jazyky, rozpoznávané NFA
M1 = (Q1, Σ1, δ1, q1, F1) a M2 = (Q2, Σ2, δ2, q2, F2), kde Q1 ∩ Q2 = ∅.
Definujeme NFA s ε-kroky M1 ⊙ M2 = (Q1 ∪ Q2, Σ1 ∪ Σ2, δ, q1, F2),
kde
δ = δ1 ∪ δ2 ∪ {((p, ε), {q2}) | p ∈ F1}.
4 / 29
Uzavřenost na zřetězení
Věta 2.52.
Třída regulárních jazyků je uzavřená na zřetězení.
Důkaz:
M1 M2
ε
ε
Nechť L1 a L2 jsou regulární jazyky, rozpoznávané NFA
M1 = (Q1, Σ1, δ1, q1, F1) a M2 = (Q2, Σ2, δ2, q2, F2), kde Q1 ∩ Q2 = ∅.
Definujeme NFA s ε-kroky M1 ⊙ M2 = (Q1 ∪ Q2, Σ1 ∪ Σ2, δ, q1, F2),
kde
δ = δ1 ∪ δ2 ∪ {((p, ε), {q2}) | p ∈ F1}.
4 / 29
Korektnost: Chceme dokázat L(M1 ⊙ M2) = L(M1).L(M2)
⊇: Nechť u ∈ L(M1), tedy ∃r ∈ F1 splňující r ∈ δ1(q1, u).
Nechť v ∈ L(M2), tedy δ2(q2, v) ∩ F2 ̸= ∅. Pak
ˆδ(q1, uv) =
p∈ˆδ(q1,u)
ˆδ(p, v) ⊇ ˆδ(r, v) ⊇ ˆδ(q2, v) = δ2(q2, v).
Protože δ2(q2, v) ∩ F2 ̸= ∅, tak ˆδ(q1, uv) ∩ F2 ̸= ∅.
Tedy uv ∈ L(M1 ⊙ M2).
⊆:
5 / 29
Uzavřenost na iteraci
Věta 2.53.
Třída regulárních jazyků je uzavřená na iteraci.
Důkaz.
M
Nechť L je regulární jazyk akceptovaný NFA M = (Q, Σ, δ, q0, F).
Uzavřenost na iteraci
Věta 2.53.
Třída regulárních jazyků je uzavřená na iteraci.
Důkaz.
M
ε
ε
Nechť L je regulární jazyk akceptovaný NFA M = (Q, Σ, δ, q0, F).
Uzavřenost na iteraci
Věta 2.53.
Třída regulárních jazyků je uzavřená na iteraci.
Důkaz.
M
ε
ε
ε
Nechť L je regulární jazyk akceptovaný NFA M = (Q, Σ, δ, q0, F).
Definujeme NFA s ε-kroky M∗ = (Q ∪ {p}, Σ, δ′
, p, {p}), kde p ̸∈ Q a
δ′
= δ ∪ {((p, ε), {q0})} ∪ {((q, ε), {p}) | q ∈ F}. 6 / 29
Uzávěrové vlastnosti regulárních jazyků - Shrnutí
7 / 29
Regulární výrazy
Definice 2.58.
Množina regulárních výrazů nad abecedou Σ, označovaná RE(Σ), je
definována induktivně takto:
1 ϵ, ∅ a a pro každé a ∈ Σ jsou regulární výrazy nad Σ
(tzv. základní regulární výrazy).
2 Jsou-li E, F regulární výrazy nad Σ, jsou také (E.F), (E + F) a
(E∗
) regulární výrazy nad Σ.
3 Každý regulární výraz vznikne po konečném počtu aplikací kroků
1-2.
8 / 29
Každý regulární výraz E nad abecedou Σ popisuje (jednoznačně
určuje) jazyk L(E) nad abecedou Σ podle těchto pravidel:
L(ϵ)
def
= {ε}
L(∅)
def
= ∅
L(a)
def
= {a} pro každé a ∈ Σ
L( E.F )
def
= L(E).L(F)
L( E + F )
def
= L(E) ∪ L(F)
L( E∗
)
def
= L(E)∗
9 / 29
Rozšířené regulární výrazy v UNIXu
. = a1| . . . |an kde Σ = {a1, . . . an}
[a1 . . . an] = a1| . . . |an
[ˆa1 . . . an] = b1| . . . |bm kde {b1, . . . , bm} = Σ \ {a1, . . . an}
α? = ϵ|α
α+ = αα∗
α{n} = α . . . α (n kopií)
a mnoho dalších
Matchers: GNU grep, Google RE2, Intel Hyperscan
10 / 29
Převod regulárních výrazů na konečné automaty
RE DFA NFA NFA s ε-kroky
Věta 2.43 Věta 2.48
11 / 29
Převod regulárních výrazů na konečné automaty
RE DFA NFA NFA s ε-kroky
Věta 2.43 Věta 2.48
Věta 2.60.
Nechť E je regulární výraz. Pak existuje konečný automat
rozpoznávající L(E).
11 / 29
Převod regulárních výrazů na konečné automaty
RE DFA NFA NFA s ε-kroky
Věta 2.43 Věta 2.48
Věta 2.60.
Nechť E je regulární výraz. Pak existuje konečný automat
rozpoznávající L(E).
Důkaz. Pro libovolnou abecedu Σ lze zkonstruovat konečné
automaty, které rozpoznávají jazyky popsané základními regulárními
výrazy, tj. ∅, {ε} a {a} pro každé a ∈ Σ. Tvrzení věty pak plyne z
uzavřenosti jazyků rozpoznatelných konečnými automaty vůči
operacím sjednocení, zřetězení a iteraci.
11 / 29
Příklad
12 / 29
Konzervativní rozšíření: Regulární přechodový graf
Definice 2.64.
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ů.
13 / 29
Konzervativní rozšíření: Regulární přechodový graf
Definice 2.64.
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ů.
Slovo w ∈ Σ∗
je akceptováno grafem M, právě když
existuje posloupnost stavů q0, . . . , qn, kde n ≥ 0, q0 ∈ I, qn ∈ F
a δ(qi−1, qi ) je definováno pro každé 0 < i ≤ n
taková, že
w lze rozdělit na n částí w = v1 . . . vn tak, že
vi ∈ L(δ(qi−1, qi )) pro každé 0 < i ≤ n.
(Zjm. pokud I ∩ F ̸= ∅, tak je ε akceptováno.)
13 / 29
Převod regulárního přechodového grafu na NFA
Věta 2.65.
Pro libovolný regulární přechodový graf M = (Q, Σ, δ, I, F) existuje
ekvivalentní NFA M′
s ε-kroky.
Důkaz. Algoritmus konstrukce NFA M′
s ε-kroky.
Krok 1: Ke grafu M přidáme nový stav q0 a hranu q0
ε
→ q pro každé
q ∈ I. Stav q0 bude (jediným) počátečním stavem automatu M′
, prvky
F jeho koncovými stavy.
14 / 29
Krok 2: Opakovaně realizuj kroky (a) a (b) dokud přechodový graf
obsahuje alespoň jednu hranu ohodnocenou symbolem, který nepatří
do Σ ∪ {ε}, tedy je tvaru F + G, F.G, F∗
nebo ∅.
(a) Odstraň všechny hrany, které jsou ohodnoceny symbolem ∅.
(b) Vyber libovolnou hranu p
E
→ q, kde E ̸∈ Σ ∪ {ε}, odstraň ji a
proveď následující:
p q
F + G
=⇒
Krok 2: Opakovaně realizuj kroky (a) a (b) dokud přechodový graf
obsahuje alespoň jednu hranu ohodnocenou symbolem, který nepatří
do Σ ∪ {ε}, tedy je tvaru F + G, F.G, F∗
nebo ∅.
(a) Odstraň všechny hrany, které jsou ohodnoceny symbolem ∅.
(b) Vyber libovolnou hranu p
E
→ q, kde E ̸∈ Σ ∪ {ε}, odstraň ji a
proveď následující:
p q
F + G
=⇒ p q
F
G
p qF.G
=⇒
Krok 2: Opakovaně realizuj kroky (a) a (b) dokud přechodový graf
obsahuje alespoň jednu hranu ohodnocenou symbolem, který nepatří
do Σ ∪ {ε}, tedy je tvaru F + G, F.G, F∗
nebo ∅.
(a) Odstraň všechny hrany, které jsou ohodnoceny symbolem ∅.
(b) Vyber libovolnou hranu p
E
→ q, kde E ̸∈ Σ ∪ {ε}, odstraň ji a
proveď následující:
p q
F + G
=⇒ p q
F
G
p qF.G
=⇒ p s qF G
p qF∗
=⇒
Krok 2: Opakovaně realizuj kroky (a) a (b) dokud přechodový graf
obsahuje alespoň jednu hranu ohodnocenou symbolem, který nepatří
do Σ ∪ {ε}, tedy je tvaru F + G, F.G, F∗
nebo ∅.
(a) Odstraň všechny hrany, které jsou ohodnoceny symbolem ∅.
(b) Vyber libovolnou hranu p
E
→ q, kde E ̸∈ Σ ∪ {ε}, odstraň ji a
proveď následující:
p q
F + G
=⇒ p q
F
G
p qF.G
=⇒ p s qF G
p qF∗
=⇒ p s qε
F
ε
15 / 29
Konečnost algoritmu M obsahuje pouze konečně mnoho hran,
tj. konečně mnoho regulárních výrazů. Každý regulární výraz
obsahuje jen konečně mnoho výskytů +, . a ∗
. V každém kroku 2(b)
jeden výskyt odstraníme.
Korektnost algoritmu
Výsledný graf je přechodovým grafem nedeterministického
konečného automatu M′
s ε-kroky.
Přímo z definice regulárního přechodového grafu se snadno
ověří, že kroky 1 a 2 popsaného transformačního algoritmu
zachovávají ekvivalenci automatů, proto L(M) = L(M′
).
16 / 29
Převod DFA na regulární výraz
Věta 2.66.
Pro každý regulární přechodový graf M = (Q, Σ, δ, I, F) existuje
ekvivalentní přechodový graf M′
= ({x, y}, Σ, δ′
, {x}, {y}).
Důsledky
Na regulární výraz lze převést každý konečný automat (zjm.
DFA).
Regulární jazyky jsou uzavřeny na substituci (a tedy i
homomorfismus).
17 / 29
Převod DFA na regulární výraz
Věta 2.66.
Pro každý regulární přechodový graf M = (Q, Σ, δ, I, F) existuje
ekvivalentní přechodový graf M′
= ({x, y}, Σ, δ′
, {x}, {y}).
Důsledky
Na regulární výraz lze převést každý konečný automat (zjm.
DFA).
Regulární jazyky jsou uzavřeny na substituci (a tedy i
homomorfismus).
Důkaz. Algoritmus transformace:
Krok 1: Ke grafu M přidáme nový počáteční stav x a nový koncový
stav y. Přidáme také hrany x
ε
→ q pro každé q ∈ I a r
ε
→ y pro každé
r ∈ F.
17 / 29
Krok 2: Každý stav p různý od x, y nyní odstraníme spolu s hranami,
které do p vcházejí nebo z p vycházejí:
a Pokud do p nevede hrana z jiného uzlu, je nedosažitelný
z počátečního stavu.
b Pokud z p nevede hrana do jiného uzlu, nelze z p dosáhnout
koncový stav.
V obou případech p odstraníme bez náhrady.
Dále:
18 / 29
Krok 2: Každý stav p různý od x, y nyní odstraníme spolu s hranami,
které do p vcházejí nebo z p vycházejí:
a Pokud do p nevede hrana z jiného uzlu, je nedosažitelný
z počátečního stavu.
b Pokud z p nevede hrana do jiného uzlu, nelze z p dosáhnout
koncový stav.
V obou případech p odstraníme bez náhrady.
Dále:
r p qF G
=⇒ r qF.G
r p qF
E
G
=⇒ r qF.E∗.G
18 / 29
r1
p
q1
r2 q2
F1 G1
E
F2 G2
−→
r1 q1
r2 q2
F1.E∗.G1
F2.E∗.G2
F1.E∗.G2
F2.E∗.G1
Po odstranění všech stavů různých od x a y zůstanou tyto dva stavy
spolu s (žádnou nebo jednou) hranou z x do y.
Konečnost algoritmu Každým krokem 2 snížíme počet stavů.
Korektnost algoritmu Z definice regulárního přechodového grafu
přímo ověříme, že kroky 1 i 2 zachovávají ekvivalenci.
19 / 29
Ekvivalence konečných automatů a reg. výrazů
RE DFA NFA NFA s ε-kroky
Věta 2.66 Věta 2.43 Věta 2.48
Věta 2.60, Věta 2.65
Věta 2.63 – Kleeneho věta (1956)
Libovolný jazyk je popsatelný regulárním výrazem právě když je
rozpoznatelný konečným automatem.
Ekvivalentní formulace: Třída jazyků rozpoznatelných konečnými
automaty je nejmenší třída, která obsahuje všechny konečné množiny
a je uzavřena na sjednocení, zřetězení a iteraci.
Ekvivalence konečných automatů a reg. výrazů
RE DFA NFA NFA s ε-kroky
Věta 2.66 Věta 2.43 Věta 2.48
Věta 2.60, Věta 2.65
Reg. gramatiky
Věta 2.63 – Kleeneho věta (1956)
Libovolný jazyk je popsatelný regulárním výrazem právě když je
rozpoznatelný konečným automatem.
Ekvivalentní formulace: Třída jazyků rozpoznatelných konečnými
automaty je nejmenší třída, která obsahuje všechny konečné množiny
a je uzavřena na sjednocení, zřetězení a iteraci.
20 / 29
Převod regulární gramatiky na konečný automat
Lemma 2.69.
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:
21 / 29
Převod regulární gramatiky na konečný automat
Lemma 2.69.
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:
Konstrukce konečného automatu M = (Q, Σ, δ, q0, F)
Q = {A | A ∈ N} ∪ {qf }, kde qf ̸∈ N
q0 = S
δ je nejmenší funkce Q × Σ → 2Q
splňující:
– pokud A → aB je pravidlo v P, pak B ∈ δ(A, a)
– pokud A → a je pravidlo v P, kde a ̸= ε, pak qf ∈ δ(A, a)
F =
{S, qf } pokud S → ε je pravidlo v P
{qf } jinak
21 / 29
Korektnost Nejprve indukcí vzhledem ke k dokážeme, že pro každé
a1, . . . , ak ∈ Σ a B ∈ N platí:
S ⇒∗
a1 . . . ak B ⇐⇒ B ∈ ˆδ(S, a1 . . . ak )
Základní krok k = 0: Z definice ˆδ plyne ˆδ(S, ε) = {S} a proto:
S ⇒∗
B ⇐⇒ B = S ⇐⇒ B = S ⇐⇒ B ∈ ˆδ(S, ε)
Indukční krok:
S ⇒∗
a1 . . . ak+1B
⇐⇒ ∃C ∈ N takové, že S ⇒∗
a1 . . . ak C ⇒ a1 . . . ak+1B
⇐⇒ ∃C ∈ N takové, že C ∈ ˆδ(S, a1 . . . ak ) ∧ C → ak+1B
⇐⇒ ∃C ∈ N takové, že C ∈ ˆδ(S, a1 . . . ak ) ∧ B ∈ δ(C, ak+1)
⇐⇒ B ∈ ˆδ(S, a1 . . . ak+1).
22 / 29
Dokázali jsme: S ⇒∗
a1 . . . ak B ⇐⇒ B ∈ ˆδ(S, a1 . . . ak )
Ukážeme, že w ∈ L(G) ⇐⇒ w ∈ L(M):
w = ε:
ε ∈ L(G) ⇐⇒ S → ε ∈ P ⇐⇒ S ∈ F ⇐⇒ ε ∈ L(M)
w = va, kde v ∈ Σ∗
, a ∈ Σ:
va ∈ L(G) ⇐⇒ S ⇒∗
vB ⇒ va
⇐⇒ S ⇒∗
vB ∧ B → a ∈ P
⇐⇒ B ∈ ˆδ(S, v) ∧ qf ∈ δ(B, a)
⇐⇒ qf ∈ ˆδ(S, va) ⇐⇒ va ∈ L(M)
23 / 29
Převod konečného automatu na regulární gramatiku
Lemma 2.71
Pro každý konečný automat M = (Q, Σ, δ, q0, F) existuje regulární
gramatika G = (N, Σ, P, S) taková, že L(M) = L(G).
Důkaz:
24 / 29
Převod konečného automatu na regulární gramatiku
Lemma 2.71
Pro každý konečný automat M = (Q, Σ, δ, q0, F) existuje regulární
gramatika G = (N, Σ, P, S) taková, že L(M) = L(G).
Důkaz:
Bez újmy na obecnosti předpokládejme, že M je nedeterministický.
N = {q | q ∈ Q} ∪ {S}, kde S ̸∈ Q.
P je nejmenší množina pravidel splňující:
– pokud p ∈ δ(q, a), je q → ap pravidlo v P
– pokud p ∈ δ(q, a) a p ∈ F, je q → a pravidlo v P
– pokud p ∈ δ(q0, a), je S → ap pravidlo v P
– pokud p ∈ δ(q0, a) a p ∈ F, je S → a pravidlo v P
– pokud q0 ∈ F, je S → ε pravidlo v P
24 / 29
Převod konečného automatu na regulární gramatiku
Lemma 2.71
Pro každý konečný automat M = (Q, Σ, δ, q0, F) existuje regulární
gramatika G = (N, Σ, P, S) taková, že L(M) = L(G).
Důkaz:
Bez újmy na obecnosti předpokládejme, že M je nedeterministický.
N = {q | q ∈ Q} ∪ {S}, kde S ̸∈ Q.
P je nejmenší množina pravidel splňující:
– pokud p ∈ δ(q, a), je q → ap pravidlo v P
– pokud p ∈ δ(q, a) a p ∈ F, je q → a pravidlo v P
– pokud p ∈ δ(q0, a), je S → ap pravidlo v P
– pokud p ∈ δ(q0, a) a p ∈ F, je S → a pravidlo v P
– pokud q0 ∈ F, je S → ε pravidlo v P
Gramatika G = (N, Σ, P, S) je zřejmě regulární.
Platí: ˆδ(q0, a1 . . . ak ) ∩ F ̸= ∅, kde k ≥ 0, a1, . . . , ak ∈ Σ
⇐⇒ S ⇒∗
a1 . . . ak 24 / 29
Rozhodnutelné problémy pro třídu reg. jazyků
Regulární jazyk – popsaný některým z uvažovaných formalismů,
zjm. konečným automatem
Otázky: Máme-li dány konečné automaty M a M′
nad Σ
ekvivalence: jsou M a M′
ekvivalentní? (platí L(M)=L(M′
) ?)
inkluze (jazyků): platí L(M) ⊆ L(M′
)?
příslušnost (slova k jazyku): je-li dáno w ∈ Σ∗
, platí w ∈ L(M)?
prázdnost (jazyka): je L(M) = ∅?
univerzalita (jazyka): je L(M) = Σ∗
?
konečnost (jazyka): je L(M) konečný jazyk?
25 / 29
Prázdnost, univerzalita, ekvivalence
Věta 2.74
Problém prázdnosti (L(M)
?
= ∅) a problém univerzality (L(M)
?
= Σ∗
)
jsou rozhodnutelné pro regulární jazyky.
26 / 29
Prázdnost, univerzalita, ekvivalence
Věta 2.74
Problém prázdnosti (L(M)
?
= ∅) a problém univerzality (L(M)
?
= Σ∗
)
jsou rozhodnutelné pro regulární jazyky.
Důkaz. L(M) je prázdný, právě když mezi dosažitelnými stavy
automatu M není žádný koncový stav.
26 / 29
Prázdnost, univerzalita, ekvivalence
Věta 2.74
Problém prázdnosti (L(M)
?
= ∅) a problém univerzality (L(M)
?
= Σ∗
)
jsou rozhodnutelné pro regulární jazyky.
Důkaz. L(M) je prázdný, právě když mezi dosažitelnými stavy
automatu M není žádný koncový stav.
Univerzalita: L(M) = Σ∗
⇐⇒ co−L(M) = ∅.
26 / 29
Prázdnost, univerzalita, ekvivalence
Věta 2.74
Problém prázdnosti (L(M)
?
= ∅) a problém univerzality (L(M)
?
= Σ∗
)
jsou rozhodnutelné pro regulární jazyky.
Důkaz. L(M) je prázdný, právě když mezi dosažitelnými stavy
automatu M není žádný koncový stav.
Univerzalita: L(M) = Σ∗
⇐⇒ co−L(M) = ∅.
Věta 2.77
Problém ekvivalence je rozhodnutelný pro regulární jazyky.
26 / 29
Prázdnost, univerzalita, ekvivalence
Věta 2.74
Problém prázdnosti (L(M)
?
= ∅) a problém univerzality (L(M)
?
= Σ∗
)
jsou rozhodnutelné pro regulární jazyky.
Důkaz. L(M) je prázdný, právě když mezi dosažitelnými stavy
automatu M není žádný koncový stav.
Univerzalita: L(M) = Σ∗
⇐⇒ co−L(M) = ∅.
Věta 2.77
Problém ekvivalence je rozhodnutelný pro regulární jazyky.
Důkaz. Pro libovolné L1, L2 platí:
(L1 =L2) ⇐⇒ (L1 ∩ co−L2) ∪ (co−L1 ∩ L2) = ∅.
Pro L1, L2 zadané automaty lze uvedené operace algoritmicky
realizovat.
26 / 29
Prázdnost, univerzalita, ekvivalence
Věta 2.74
Problém prázdnosti (L(M)
?
= ∅) a problém univerzality (L(M)
?
= Σ∗
)
jsou rozhodnutelné pro regulární jazyky.
Důkaz. L(M) je prázdný, právě když mezi dosažitelnými stavy
automatu M není žádný koncový stav.
Univerzalita: L(M) = Σ∗
⇐⇒ co−L(M) = ∅.
Věta 2.77
Problém ekvivalence je rozhodnutelný pro regulární jazyky.
Důkaz. Pro libovolné L1, L2 platí:
(L1 =L2) ⇐⇒ (L1 ∩ co−L2) ∪ (co−L1 ∩ L2) = ∅.
Pro L1, L2 zadané automaty lze uvedené operace algoritmicky
realizovat.
Alternativně: minimalizace a kanonizace.
26 / 29
Prázdnost, univerzalita, ekvivalence
Věta 2.74
Problém prázdnosti (L(M)
?
= ∅) a problém univerzality (L(M)
?
= Σ∗
)
jsou rozhodnutelné pro regulární jazyky.
Důkaz. L(M) je prázdný, právě když mezi dosažitelnými stavy
automatu M není žádný koncový stav.
Univerzalita: L(M) = Σ∗
⇐⇒ co−L(M) = ∅.
Věta 2.77
Problém ekvivalence je rozhodnutelný pro regulární jazyky.
Důkaz. Pro libovolné L1, L2 platí:
(L1 =L2) ⇐⇒ (L1 ∩ co−L2) ∪ (co−L1 ∩ L2) = ∅.
Pro L1, L2 zadané automaty lze uvedené operace algoritmicky
realizovat.
Alternativně: minimalizace a kanonizace.
Inkluze, příslušnost
26 / 29
Konečnost
Věta 2.76
Problém, zda jazyk L zadaný automatem M je konečný,
resp. nekonečný, je rozhodnutelný.
Důkaz. Nechť M je DFA. L je nekonečný právě když M akceptuje
alespoň jedno slovo w ∈ Σ∗
s vlastností n ≤ |w| < 2n, kde
n = card(Q).
27 / 29
Konečnost
Věta 2.76
Problém, zda jazyk L zadaný automatem M je konečný,
resp. nekonečný, je rozhodnutelný.
Důkaz. Nechť M je DFA. L je nekonečný právě když M akceptuje
alespoň jedno slovo w ∈ Σ∗
s vlastností n ≤ |w| < 2n, kde
n = card(Q).
(⇐=) Je-li |w| ≥ n, pak M při čtení w musí projít dvakrát stejným
stavem.
Proto w = xyz tak, že |y| ≥ 1 a platí xyi
z ∈ L pro každé i ∈ N0 (viz
důkaz lemmatu o vkládání), tedy L je nekonečný.
(=⇒) Je-li L nekonečný, pak existuje u ∈ L takové, že |u| ≥ n. Je-li
|u| < 2n, jsme hotovi. Nechť |u| ≥ 2n. Z lemma o vkládání plyne, že
u = xyz, kde 1 ≤ |y| ≤ n a xz ∈ L. Platí |xz| ≥ n. Pokud |xz| ≥ 2n, celý
postup opakujeme.
Existenci w ∈ L takového, že n ≤ |w| < 2n, lze algoritmicky ověřit
(slov je konečně mnoho,„vyzkoušíme“ každé z nich).
27 / 29
Aplikace reg. jazyků a konečných automatů
Vyhledávání vzorů (pattern matching) v textu (editory,
textové systémy), DNA sekvencích, . . .
Například v Unixu:
grep - vyhledávání podle zadaného regulárního výrazu
egrep - vyhledávání podle zadaného rozšířeného regulárního
výrazu
fgrep - vyhledávání podle zadaného řetězce
Zpracování lexikálních jednotek například při automatizované
konstrukci překladačů (lex, flex)
Zpracování obrazů (image processing)
Konečné automaty nad nekonečnými slovy
Specifikace a verifikace konečně stavových systémů
Konečné automaty s výstupem
28 / 29
Verifikace: Příklad
29 / 29
Verifikace: Příklad
29 / 29