Formální jazyky a automaty
Uzávěrové vlastnosti a (ne)rozhodnutelné problémy pro CFL,
deterministické CFL, Turingovy stroje
Jan Křetínský
Fakulta informatiky, MU Brno
Jaro 2024
Vlastnosti bezkontextových jazyků
Věta 3.58. (a 3.61.)
Třída bezkontextových jazyků (L2) je uzavřena vzhledem k operacím:
. . .
Věta 3.60.
Třída bezkontextových jazyků (L2) není uzavřena vzhledem
k operacím:
. . .
2 / 23
Sjednocení
L1 je generován CFG G1 = (N1, Σ1, P1, S1) a
L2 je generován CFG G2 = (N2, Σ2, P2, S2).
Bez újmy na obecnosti můžeme předpokládat N1 ∩ N2 = ∅.
3 / 23
Sjednocení
L1 je generován CFG G1 = (N1, Σ1, P1, S1) a
L2 je generován CFG G2 = (N2, Σ2, P2, S2).
Bez újmy na obecnosti můžeme předpokládat N1 ∩ N2 = ∅.
Definujeme G = (N1 ∪ N2 ∪ {S}, Σ1 ∪ Σ2, P, S), kde S je nový symbol a
P = P1 ∪ P2 ∪ {S → S1, S → S2}.
Každá derivace v G začne použitím buď S → S1 nebo S → S2.
Podmínka N1 ∩ N2 = ∅ zaručí, že při použití S → S1 (resp. S → S2) lze
v dalším derivování používat jen pravidla z P1 (resp. P2).
Jazyk L = L1 ∪ L2 je generován gramatikou G.
3 / 23
Zřetězení
L1 je generován CFG G1 = (N1, Σ1, P1, S1) a
L2 je generován CFG G2 = (N2, Σ2, P2, S2).
Bez újmy na obecnosti můžeme předpokládat N1 ∩ N2 = ∅.
4 / 23
Zřetězení
L1 je generován CFG G1 = (N1, Σ1, P1, S1) a
L2 je generován CFG G2 = (N2, Σ2, P2, S2).
Bez újmy na obecnosti můžeme předpokládat N1 ∩ N2 = ∅.
Definujeme G = (N1 ∪ N2 ∪ {S}, Σ1 ∪ Σ2, P, S), kde S je nový symbol a
P = P1 ∪ P2 ∪ {S → S1S2}.
Jazyk L = L1.L2 je generován gramatikou G.
4 / 23
Iterace a pozitivní iterace
L1 je generován CFG G1 = (N1, Σ1, P1, S1).
5 / 23
Iterace a pozitivní iterace
L1 je generován CFG G1 = (N1, Σ1, P1, S1).
Definujeme G = (N1 ∪ {S}, Σ1, P, S), kde S je nový symbol a
P = P1 ∪ {S → SS1 | ε}.
Jazyk L = L∗
1 je generován gramatikou G.
Definujeme G = (N1 ∪ {S}, Σ1, P, S), kde S je nový symbol a
P = P1 ∪ {S → SS1 | S1}.
Jazyk L = L+
1 je generován gramatikou G.
5 / 23
Průnik
L1 = {an
bn
cm
| m, n ≥ 1} L2 = {an
bm
cn
| m, n ≥ 1}
Oba tyto jazyky jsou CFL.
Kbyby L2 byla uzavřena vzhledem k operaci průniku, pak by i
L1 ∩ L2 = {an
bn
cn
| n ≥ 1} musel být bezkontextový, což však není.
6 / 23
Doplněk
Neuzavřenost L2 vůči doplňku plyne z její uzavřenosti na sjednocení,
neuzavřenosti na průnik a z De Morganových pravidel:
L1 ∩ L2 = co−(co−L1 ∪ co−L2),
tj., kdyby L2 byla uzavřena na doplněk, musela by být uzavřena i na
průnik, což však není.
7 / 23
Doplněk
Neuzavřenost L2 vůči doplňku plyne z její uzavřenosti na sjednocení,
neuzavřenosti na průnik a z De Morganových pravidel:
L1 ∩ L2 = co−(co−L1 ∪ co−L2),
tj., kdyby L2 byla uzavřena na doplněk, musela by být uzavřena i na
průnik, což však není.
(Další) protipříklad k uzavřenosti na doplněk:
L = {ww | w ∈ {a, b}∗
} není CFL.
co−L je CFL.
7 / 23
Průnik s regulárním jazykem
L = L(P), kde P je PDA P = (Q1, Σ, Γ, δ1, q1, Z0, F1)
R = L(A), kde A je deterministický FA A = (Q2, Σ, δ2, q2, F2)
Sestrojíme PDA P′
takový, že L(P′
) = L ∩ R.
P′
= (Q, Σ, Γ, δ, q0, Z0, F), kde
▶ Q = Q1 × Q2
▶ q0 = ⟨q1, q2⟩
▶ F = F1 × F2
▶ δ : pro každé p ∈ Q1, q ∈ Q2, a ∈ Σ ∪ {ε}, Z ∈ Γ platí:
δ(⟨p, q⟩, a, Z) = {(⟨p′
, q′
⟩, γ) | (p′
, γ) ∈ δ1(p, a, Z) a δ2(q, a) = q′
}
Zřejmě platí w ∈ L(P′
) ⇐⇒ w ∈ L(P) ∩ L(A).
8 / 23
Vlastnosti bezkontextových jazyků
Věta 3.58. (a 3.61.)
Třída bezkontextových jazyků (L2) je uzavřena vzhledem k operacím:
1. sjednocení
2. zřetězení
3. iterace
4. pozitivní iterace
5. průnik s regulárním jazykem
Věta 3.60.
Třída bezkontextových jazyků (L2) není uzavřena vzhledem
k operacím:
1. průnik
2. doplněk
9 / 23
Rozhodnutelné problémy pro bezkontextové jazyky
Problém příslušnosti
Existuje algoritmus, který pro libovolnou danou CFG G a slovo w
rozhoduje, zda w ∈ L(G) či nikoliv.
Problém prázdnosti
Existuje algoritmus, který pro libovolnou danou CFG G rozhoduje,
zda L(G) = ∅ či nikoliv.
Problém konečnosti
Existuje algoritmus, který pro libovolnou danou CFG G rozhoduje,
zda L(G) je konečný či nikoliv.
10 / 23
Rozhodnutelné problémy pro bezkontextové jazyky
Problém příslušnosti
Existuje algoritmus, který pro libovolnou danou CFG G a slovo w
rozhoduje, zda w ∈ L(G) či nikoliv.
Problém prázdnosti
Existuje algoritmus, který pro libovolnou danou CFG G rozhoduje,
zda L(G) = ∅ či nikoliv.
Problém konečnosti
Existuje algoritmus, který pro libovolnou danou CFG G rozhoduje,
zda L(G) je konečný či nikoliv.
Věta 3.68.
Ke každé CFG G lze sestrojit čísla m, n taková, že L(G) je nekonečný
právě když existuje slovo z ∈ L(G) takové, že m < |z| ≤ n.
Důkaz: pomocí Lemmatu o vkládání, analogicky regulárnímu případu.
10 / 23
Vlastnost sebevložení
Definice 3.70.
Nechť G = (N, Σ, P, S) je CFG. Řekneme, že G má vlastnost
sebevložení, jestliže existují A ∈ N a u, v ∈ Σ+
taková, že A ⇒+
uAv.
CFL L má vlastnost sebevložení, jestliže každá bezkontextová
gramatika, která jej generuje, má vlastnost sebevložení.
Věta 3.71.
CFL L má vlastnost sebevložení, právě když L není regulární.
Důkaz. Viz skripta.
11 / 23
Nerozhodnutelné problémy pro bezkontextové jazyky
Problém regularity
Neexistuje algoritmus, který pro libovolnou danou CFG G rozhoduje,
zda L(G) je regulární či nikoliv.
(Tedy není rozhodnutelné, zda L(G) má vlastnost sebevložení či
nikoliv.)
Problém univerzality
Neexistuje algoritmus, který pro libovolnou danou CFG G rozhoduje,
zda L(G) = Σ∗
či nikoliv.
Problémy ekvivalence a inkluze také nejsou rozhodnutelné (plyne
z nerozhodnutelnosti problému univerzality).
12 / 23
Deterministické zásobníkové automaty
Definice 3.72.
Řekneme, že PDA M = (Q, Σ, Γ, δ, q0, Z0, F) je deterministický
(DPDA), jestliže jsou splněny tyto podmínky:
1. pro žádné q ∈ Q, Z ∈ Γ a a ∈ Σ ∪ {ε} neobsahuje δ(q, a, Z) více
než jeden prvek
2. pro všechna q ∈ Q a Z ∈ Γ platí:
kdykoliv δ(q, ε, Z) ̸= ∅, pak δ(q, a, Z) = ∅ pro všechna a ∈ Σ
Řekneme, že L je deterministický bezkontextový jazyk (DCFL), právě
když existuje DPDA M takový, že L = L(M).
13 / 23
Vlastnosti deterministických bezkontextových jazyků
Věta 3.82.
Třída DCFL je uzavřena na doplňek.
Intuice:
▶ DPDA má nad každým slovem právě jeden výpočet.
▶ Pro doplňek stačí zaměnit koncové a nekoncové stavy.
14 / 23
Vlastnosti deterministických bezkontextových jazyků
Věta 3.82.
Třída DCFL je uzavřena na doplňek.
Intuice:
▶ DPDA má nad každým slovem právě jeden výpočet.
▶ Pro doplňek stačí zaměnit koncové a nekoncové stavy.
▶ Musí dočíst vstup až do konce!
DPDA by nemusel dočíst vstupní slovo do konce, protože
▶ se vyprázdní zásobník nebo přechod není definován
14 / 23
Vlastnosti deterministických bezkontextových jazyků
Věta 3.82.
Třída DCFL je uzavřena na doplňek.
Intuice:
▶ DPDA má nad každým slovem právě jeden výpočet.
▶ Pro doplňek stačí zaměnit koncové a nekoncové stavy.
▶ Musí dočíst vstup až do konce!
DPDA by nemusel dočíst vstupní slovo do konce, protože
▶ se vyprázdní zásobník nebo přechod není definován
▶ přestane číst vstup a jen provádí ε-kroky pod kterýmy zásobník
neomezeně roste
14 / 23
Vlastnosti deterministických bezkontextových jazyků
Věta 3.82.
Třída DCFL je uzavřena na doplňek.
Intuice:
▶ DPDA má nad každým slovem právě jeden výpočet.
▶ Pro doplňek stačí zaměnit koncové a nekoncové stavy.
▶ Musí dočíst vstup až do konce!
DPDA by nemusel dočíst vstupní slovo do konce, protože
▶ se vyprázdní zásobník nebo přechod není definován
▶ přestane číst vstup a jen provádí ε-kroky pod kterýmy zásobník
neomezeně roste
14 / 23
Vlastnosti deterministických bezkontextových jazyků
Věta 3.82.
Třída DCFL je uzavřena na doplňek.
Intuice:
▶ DPDA má nad každým slovem právě jeden výpočet.
▶ Pro doplňek stačí zaměnit koncové a nekoncové stavy.
▶ Musí dočíst vstup až do konce!
DPDA by nemusel dočíst vstupní slovo do konce, protože
▶ se vyprázdní zásobník nebo přechod není definován
▶ přestane číst vstup a jen provádí ε-kroky pod kterýmy zásobník
neomezeně roste ⇐⇒ vzroste o |Q| · |Γ| · max.délka pravidla
14 / 23
Vlastnosti deterministických bezkontextových jazyků
Věta 3.82.
Třída DCFL je uzavřena na doplňek.
Intuice:
▶ DPDA má nad každým slovem právě jeden výpočet.
▶ Pro doplňek stačí zaměnit koncové a nekoncové stavy.
▶ Musí dočíst vstup až do konce!
DPDA by nemusel dočíst vstupní slovo do konce, protože
▶ se vyprázdní zásobník nebo přechod není definován
▶ přestane číst vstup a jen provádí ε-kroky pod kterýmy zásobník
neomezeně roste ⇐⇒ vzroste o |Q| · |Γ| · max.délka pravidla
▶ cyklí
14 / 23
Vlastnosti deterministických bezkontextových jazyků
Věta 3.82.
Třída DCFL je uzavřena na doplňek.
Intuice:
▶ DPDA má nad každým slovem právě jeden výpočet.
▶ Pro doplňek stačí zaměnit koncové a nekoncové stavy.
▶ Musí dočíst vstup až do konce!
DPDA by nemusel dočíst vstupní slovo do konce, protože
▶ se vyprázdní zásobník nebo přechod není definován
▶ přestane číst vstup a jen provádí ε-kroky pod kterýmy zásobník
neomezeně roste ⇐⇒ vzroste o |Q| · |Γ| · max.délka pravidla
▶ cyklí
▶ dočte slovo, ale pak pod ε-kroky prochází koncové i nekoncové
stavy (tj. některá slova jsou akceptována původním DPDA
i DPDA se zaměněnými koncovými stavy).
14 / 23
Průnik a sjednocení
Věta.
Třída DCFL není uzavřena na průnik.
Věta 3.84.
Třída DCFL není uzavřena na sjednocení.
Důkaz. Plyne z uzavřenosti na doplňek, neuzavřenosti na průnik a
z De Morganových pravidel:
L1 ∩ L2 = co−(co−L1 ∪ co−L2)
(Z uzavřenosti na sjednocení by plynula uzavřenost na průnik.)
Věta 3.86.
Třída DCFL tvoří vlastní podtřídu třídy bezkontextových jazyků.
Příklad. Jazyk co−{ww | w ∈ {a, b}∗
} je CFL, ale není DCFL.
15 / 23
Aplikace (deterministických) bezkontextových jazyků
▶ syntaxe programovacích jazyků je definována pomocí CFG
(dobře uzávorkované výrazy, if–then–else konstrukty)
▶ DTD (Document Type definition) umožňuje definovat
bezkontexové jazyky – využití ve značkovacích jazycích (HTML,
XML,. . . )
▶ nástroje pro tvorbu parserů/překladačů využívají různé algoritmy
pro lineární deterministickou syntaktickou analýzu:
LALR(1) - Yacc, Bison, javacup
LL(k) - JavaCC, ANTLR
16 / 23
Turingův stroj
17 / 23
Turingův stroj
Definice (Syntax)
(Deterministický) Turingův stroj (Turing Machine, TM) je devítice
M = (Q, Σ, Γ, ▷, ⊔, δ, q0, qacc, qrej), kde
▶ Q je konečná množina, jejíž prvky nazýváme stavy,
▶ Σ je konečná množina, tzv. vstupní abeceda,
▶ Γ je konečná množina, tzv. pracovní abeceda, Σ ⊆ Γ,
▶ ▷ ∈ Γ ∖ Σ je levá koncová značka,
▶ ⊔ ∈ Γ ∖ Σ je symbol označující prázdné políčko,
▶ δ : (Q ∖ {qacc, qrej}) × Γ → Q × Γ × {L, R}
je totální přechodová funkce,
▶ q0 ∈ Q je počáteční stav,
▶ qacc ∈ Q je akceptující stav,
▶ qrej ∈ Q je zamítající stav, qacc ̸= qrej
a pro každé δ(q, ▷) = (p, x, X) je x = ▷, X = R (tj. ▷ nelze přepsat
ani posunout hlavu za okraj pásky).
17 / 23
Konfigurace Turingova stroje
Definice.
Konfigurace TM je trojice (q, z, n) ∈ Q × {y⊔ω
| y ∈ Γ∗
} × N0, kde
▶ q je stav,
▶ y⊔ω
je obsah pásky, (kde ⊔ω
= ⊔ ⊔ ⊔ ⊔ ⊔ ⊔ . . .)
▶ n značí pozici hlavy na pásce.
Počáteční konfigurace pro vstup w ∈ Σ∗
je trojice (q0, ▷w⊔ω
, 0).
Akceptující konfigurace je každá trojice tvaru (qacc, z, n).
Zamítající konfigurace je každá trojice tvaru (qrej, z, n).
18 / 23
Výpočet Turingova stroje
Definice.
Na množině všech konfigurací stroje M definujeme binární relaci
krok výpočtu | M takto:
(p, z, n) | M



(q, sn
b (z), n + 1) pro δ(p, zn) = (q, b, R)
(q, sn
b (z), n − 1) pro δ(p, zn) = (q, b, L)
kde zn označuje n-tý symbol řetězu z (z0 je nejlevější symbol řetězu
z) a sn
b (z) řetěz vzniklý ze z nahrazením zn symbolem b.
19 / 23
Výpočet Turingova stroje
Definice.
Na množině všech konfigurací stroje M definujeme binární relaci
krok výpočtu | M takto:
(p, z, n) | M



(q, sn
b (z), n + 1) pro δ(p, zn) = (q, b, R)
(q, sn
b (z), n − 1) pro δ(p, zn) = (q, b, L)
kde zn označuje n-tý symbol řetězu z (z0 je nejlevější symbol řetězu
z) a sn
b (z) řetěz vzniklý ze z nahrazením zn symbolem b.
Výpočet TM M na vstupu w je maximální (konečná nebo nekonečná)
posloupnost konfigurací K0, K1, K2, . . ., kde K0 je počáteční
konfigurace pro w a Ki | M Ki+1 pro všechna i ≥ 0.
19 / 23
Jazyk Turingova stroje
Stroj M akceptuje slovo w právě když výpočet M na w je konečný a
jeho poslední konfigurace je akceptující.
Stroj M zamítá slovo w právě když výpočet M na w je konečný a
jeho poslední konfigurace je zamítající.
Stroj M pro vstup w cyklí právě když výpočet M na w je nekonečný.
Jazyk akceptovaný TM M definujeme jako
L(M) = {w ∈ Σ∗
| M akceptuje w}.
20 / 23
Jazyk Turingova stroje
Stroj M akceptuje slovo w právě když výpočet M na w je konečný a
jeho poslední konfigurace je akceptující.
Stroj M zamítá slovo w právě když výpočet M na w je konečný a
jeho poslední konfigurace je zamítající.
Stroj M pro vstup w cyklí právě když výpočet M na w je nekonečný.
Jazyk akceptovaný TM M definujeme jako
L(M) = {w ∈ Σ∗
| M akceptuje w}.
Stroj M se nazývá úplný, je-li každý jeho výpočet konečný
(akceptující nebo zamítající).
20 / 23
Příklad
L = {xux | x ∈ {a, b}, u ∈ {a, b}∗
} ∪ {a, b}
21 / 23
Příklad
L = {xux | x ∈ {a, b}, u ∈ {a, b}∗
} ∪ {a, b}
Formálně, M = (Q, Σ, Γ, ▷, ⊔, δ, s, qacc, qrej), kde
Q = {s, qacc, qrej, [q1, a], [q2, a], [q1, b], [q2, b]},
Σ = {a, b},
Γ = Σ ∪ {▷, ⊔}.
δ:
▷ a b ⊔
s (s, ▷, R) ([q1, a], a, R) ([q1, b], b, R) (qrej, −, −)
[q1, a] − ([q1, a], a, R) ([q1, a], b, R) ([q2, a], ⊔, L)
[q1, b] − ([q1, b], a, R) ([q1, b], b, R) ([q2, b], ⊔, L)
[q2, a] − (qacc, −, −) (qacc, −, −) −
[q2, b] − (qrej, −, −) (qrej, −, −) −
21 / 23
Přehled jazykových tříd
Jazyky Gramatiky (typ) Automaty
rekursivně spočetné frázové (0) Turingovy stroje
rekursivní - úplné Turingovy stroje
kontextové kontextové (1) lineárně ohraničené TM
bezkontextové bezkontextové (2) zásobníkové automaty
deterministické CFL - deterministické PDA
regulární regulární (3) konečné automaty
Třída na nižším řádku je vždy vlastní podtřídou třídy na vyšším řádku.
22 / 23
Uzávěrové vlastnosti
Věta 4.16.
Třída rekurzivních jazyků je uzavřena vzhledem k operaci
komplementu.
23 / 23
Uzávěrové vlastnosti
Věta 4.16.
Třída rekurzivních jazyků je uzavřena vzhledem k operaci
komplementu.
Věta 4.17.
Pokud jsou L i co−L oba rekurzivně spočetné, pak jsou oba rekurzivní.
23 / 23
Uzávěrové vlastnosti
Věta 4.16.
Třída rekurzivních jazyků je uzavřena vzhledem k operaci
komplementu.
Věta 4.17.
Pokud jsou L i co−L oba rekurzivně spočetné, pak jsou oba rekurzivní.
Věta 4.15.
Třídy rekurzivních a rekurzivně spočetných jazyků jsou uzavřeny
vzhledem k operacím sjednocení, průniku, zřetězení a iteraci.
23 / 23