Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Bezkontextové jazyky
Uzávěrové vlastnosti
Šárka Vavrečková
Ústav informatiky, FPF SU Opava
Poslední aktualizace: 20. října 2008
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Porovnání důkazů uzávěrových vlastností
Co to je?
Třída jazyků je uzavřena vůči dané operaci, pokud po uplatnění
této operace na kterékoliv jazyky z dané třídy vznikne opět jazyk z
této třídy jazyků.
Postup důkazu
u regulárních jazyků: důkazy pomocí automatů
u bezkontextových jazyků: většinou důkazy pomocí gramatik,
jen u vztahu týkajícího se také regulárních jazyků (průnik
bezkontextového a regulárního jazyka) se používají automaty
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Značení a pojmy
Dále používáme toto značení:
L1 = L(G1), G1 = (N1, T1, P1, S1)
L2 = L(G2), G2 = (N2, T2, P2, S2), N1 ∪ N2 = ∅
vytváříme L = L(G), G = (N, T, P, S)
Regulární operace
jsou operace používané při konstrukci regulárních výrazů, tj.
sjednocení, zřetězení a iterace (Kleeneho uzávěr, operace
hvězdička).
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Sjednocení
Věta
Třída bezkontextových jazyků je uzavřena vzhledem k operaci
sjednocení.
Důkaz:
Vytvoříme gramatiku G takovou, že L(G) = L1 ∪ L2:
G = (N, T, P, S), symbol S /∈ N1 ∪ N2 (nově přidaný),
T = T1 ∪ T2,
N = N1 ∪ N2 ∪ {S},
P = P1 ∪ P2 ∪ {S → S1 S2}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Sjednocení
Věta
Třída bezkontextových jazyků je uzavřena vzhledem k operaci
sjednocení.
Důkaz:
Vytvoříme gramatiku G takovou, že L(G) = L1 ∪ L2:
G = (N, T, P, S), symbol S /∈ N1 ∪ N2 (nově přidaný),
T = T1 ∪ T2,
N = N1 ∪ N2 ∪ {S},
P = P1 ∪ P2 ∪ {S → S1 S2}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
G1 :
A → aBA CbB
B → bCb c
C → cA ε
G2 :
M → aNc ε
N → PbxM Qu b
Q → MN ab
G, kde L(G) = L(G1) ∪ L(G2):
S → A M
A → aBA CbB
B → bCb c
C → cA ε
M → aNc ε
N → PbxM Qu b
Q → MN ab
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
G1 :
A → aBA CbB
B → bCb c
C → cA ε
G2 :
M → aNc ε
N → PbxM Qu b
Q → MN ab
G, kde L(G) = L(G1) ∪ L(G2):
S → A M
A → aBA CbB
B → bCb c
C → cA ε
M → aNc ε
N → PbxM Qu b
Q → MN ab
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
Lze použít jako kritérium bezkontextovosti:
Jazyk L = {aibjck i, j, k ≥ 1, i = j nebo j = k} lze napsat jako
sjednocení dvou bezkontextových jazyků Lx ∪ Ly, kde
Lx = {aibjck i, j, k ≥ 1, i = j}
Ly = {aibjck i, j, k ≥ 1, j = k}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Zřetězení
Věta
Třída bezkontextových jazyků je uzavřena vzhledem k operaci
zřetězení.
Důkaz:
Vytvoříme gramatiku G takovou, že L(G) = L1 · L2:
N = N1 ∪ N2 ∪ {S}, S /∈ N1 ∪ N2
P = P1 ∪ P2 ∪ {S → S1 · S2}
T = T1 ∪ T2}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Zřetězení
Věta
Třída bezkontextových jazyků je uzavřena vzhledem k operaci
zřetězení.
Důkaz:
Vytvoříme gramatiku G takovou, že L(G) = L1 · L2:
N = N1 ∪ N2 ∪ {S}, S /∈ N1 ∪ N2
P = P1 ∪ P2 ∪ {S → S1 · S2}
T = T1 ∪ T2}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
G1 :
A → aBA CbB
B → bCb c
C → cA ε
G2 :
M → aNc ε
N → PbxM Qu b
Q → MN ab
G, kde L(G) = L(G1) · L(G2):
S → AM
A → aBA CbB
B → bCb c
C → cA ε
M → aNc ε
N → PbxM Qu b
Q → MN ab
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
G1 :
A → aBA CbB
B → bCb c
C → cA ε
G2 :
M → aNc ε
N → PbxM Qu b
Q → MN ab
G, kde L(G) = L(G1) · L(G2):
S → AM
A → aBA CbB
B → bCb c
C → cA ε
M → aNc ε
N → PbxM Qu b
Q → MN ab
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Iterace
Věta
Třída bezkontextových jazyků je uzavřena vzhledem k operaci
iterace (Kleeneho uzávěru, operace hvězdička).
Důkaz:
Vytvoříme gramatiku G takovou, že L(G) = L∗
1:
N = N1 ∪ {S}, S /∈ N1, T = T1,
P = P1 ∪ {S → S1S ε}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Iterace
Věta
Třída bezkontextových jazyků je uzavřena vzhledem k operaci
iterace (Kleeneho uzávěru, operace hvězdička).
Důkaz:
Vytvoříme gramatiku G takovou, že L(G) = L∗
1:
N = N1 ∪ {S}, S /∈ N1, T = T1,
P = P1 ∪ {S → S1S ε}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
G1 :
A → aBA CbB
B → bCb c
C → cA ε
G, kde L(G) = L(G1)∗:
S → AS ε
A → aBA CbB
B → bCb c
C → cA ε
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
G1 :
A → aBA CbB
B → bCb c
C → cA ε
G, kde L(G) = L(G1)∗:
S → AS ε
A → aBA CbB
B → bCb c
C → cA ε
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Věta
Třída bezkontextových jazyků je uzavřena vzhledem k operaci
pozitivní iterace.
Důkaz:
Vytvoříme gramatiku G takovou, že L(G) = L+
1 :
N = N1 ∪ {S}, S /∈ N1, T = T1,
P = P1 ∪ {S → S1S S1}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Věta
Třída bezkontextových jazyků je uzavřena vzhledem k operaci
pozitivní iterace.
Důkaz:
Vytvoříme gramatiku G takovou, že L(G) = L+
1 :
N = N1 ∪ {S}, S /∈ N1, T = T1,
P = P1 ∪ {S → S1S S1}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
G1 :
A → aBA CbB
B → bCb c
C → cA ε
G, kde L(G) = L(G1)+:
S → AS A
A → aBA CbB
B → bCb c
C → cA ε
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
G1 :
A → aBA CbB
B → bCb c
C → cA ε
G, kde L(G) = L(G1)+:
S → AS A
A → aBA CbB
B → bCb c
C → cA ε
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Zrcadlení (reverze)
Věta
Třída bezkontextových jazyků je uzavřena vzhledem k operaci
zrcadlení (reverze).
Důkaz:
Vytvoříme gramatiku G takovou, že L(G) = LR
1 :
N = N1, T = T1, S = S1
P = {A → αR (A → α) ∈ P1, A ∈ N1, α ∈ (N ∪ T)∗}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Zrcadlení (reverze)
Věta
Třída bezkontextových jazyků je uzavřena vzhledem k operaci
zrcadlení (reverze).
Důkaz:
Vytvoříme gramatiku G takovou, že L(G) = LR
1 :
N = N1, T = T1, S = S1
P = {A → αR (A → α) ∈ P1, A ∈ N1, α ∈ (N ∪ T)∗}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
G1 :
A → aBA CbB
B → bCb c
C → cA ε
G, kde L(G) = L(G1)R:
A → ABa BbC
B → bCb c
C → Ac ε
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
G1 :
A → aBA CbB
B → bCb c
C → cA ε
G, kde L(G) = L(G1)R:
A → ABa BbC
B → bCb c
C → Ac ε
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Bezkontextová substituce a homomorfismus
Věta
Třída bezkontextových jazyků je uzavřena vzhledem k operaci
bezkontextové substituce.
Co je to substituce?
Bezkontextová substituce s je takové zobrazení, které zobrazuje
každý symbol původní abecedy na bezkontextový jazyk a přitom
platí
s(ε) = ε, s(a · v) = s(a) · s(v), a ∈ (N ∪ T), v ∈ (N ∪ T)∗
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Bezkontextová substituce a homomorfismus
Věta
Třída bezkontextových jazyků je uzavřena vzhledem k operaci
bezkontextové substituce.
Co je to substituce?
Bezkontextová substituce s je takové zobrazení, které zobrazuje
každý symbol původní abecedy na bezkontextový jazyk a přitom
platí
s(ε) = ε, s(a · v) = s(a) · s(v), a ∈ (N ∪ T), v ∈ (N ∪ T)∗
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Důkaz:
L1 je bezkontextový jazyk nad abecedou Σ = {a1, a2, . . . , an},
bezkontextové jazyky J1, J2, . . . , Jn nad abecedami
Σ1, Σ2, . . . , Σn,
k nim existují bezkontextové gramatiky
GJi = (NJi , Σi, PJi , ai), v každé gramatice GJi je startovacím
symbolem ai, 1 ≤ i ≤ n,
pro každé i, 1 ≤ i ≤ n je s(ai) = Ji,
předpokládejme, že množiny neterminálních symbolů NJi jsou
po dvou disjunktní a taktéž průnik kterékoliv z těchto množin
neterminálů s množinou N1 je prázdný.
Jazyk L = s(L1) sestrojíme takto:
N = N1 ∪ {a1, a2, . . . , an} ∪ n
i=1 NJi
T = n
i=1 Σi
P = P1 ∪ n
i=1 PJi
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Důkaz:
L1 je bezkontextový jazyk nad abecedou Σ = {a1, a2, . . . , an},
bezkontextové jazyky J1, J2, . . . , Jn nad abecedami
Σ1, Σ2, . . . , Σn,
k nim existují bezkontextové gramatiky
GJi = (NJi , Σi, PJi , ai), v každé gramatice GJi je startovacím
symbolem ai, 1 ≤ i ≤ n,
pro každé i, 1 ≤ i ≤ n je s(ai) = Ji,
předpokládejme, že množiny neterminálních symbolů NJi jsou
po dvou disjunktní a taktéž průnik kterékoliv z těchto množin
neterminálů s množinou N1 je prázdný.
Jazyk L = s(L1) sestrojíme takto:
N = N1 ∪ {a1, a2, . . . , an} ∪ n
i=1 NJi
T = n
i=1 Σi
P = P1 ∪ n
i=1 PJi
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
L1 = {aibjck i, j, k ≥ 1, i = j nebo j = k}
G1 = ({S, A, B, X, Y }, {a, b, c}, P1, S) množina P1:
S → AX Y B A → aAb ab
B → bBc bc
X → cX c
Y → aY a
s(a) = {1n
n ≥ 0},
s(b) = {1n
0n
n ≥ 1},
s(c) = {0n
n ≥ 0},
GJa = ({a}, {1}, {a → 1a ε}, a)
GJb
= ({b}, {1, 0}, {b → 1b0 10}, b)
GJc = ({c}, {0}, {c → 0c ε}, c)
G = ({S, A, B, X, Y, a, b, c}, {0, 1}, P, S) množina P:
S → AX Y B
A → aAb ab
B → bBc bc
X → cX c
Y → aY a
a → 1a ε
b → 1b0 10
c → 0c ε
Generovaný jazyk je L = s(L1) = 1∗ · {1n0n n ≥ 1}∗ · 0∗
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
L1 = {aibjck i, j, k ≥ 1, i = j nebo j = k}
G1 = ({S, A, B, X, Y }, {a, b, c}, P1, S) množina P1:
S → AX Y B A → aAb ab
B → bBc bc
X → cX c
Y → aY a
s(a) = {1n
n ≥ 0},
s(b) = {1n
0n
n ≥ 1},
s(c) = {0n
n ≥ 0},
GJa = ({a}, {1}, {a → 1a ε}, a)
GJb
= ({b}, {1, 0}, {b → 1b0 10}, b)
GJc = ({c}, {0}, {c → 0c ε}, c)
G = ({S, A, B, X, Y, a, b, c}, {0, 1}, P, S) množina P:
S → AX Y B
A → aAb ab
B → bBc bc
X → cX c
Y → aY a
a → 1a ε
b → 1b0 10
c → 0c ε
Generovaný jazyk je L = s(L1) = 1∗ · {1n0n n ≥ 1}∗ · 0∗
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Průnik
Věta
Třída bezkontextových jazyků není uzavřena vzhledem k operaci
průniku.
Důkaz:
Najdeme dva bezkontextové jazyky, jejichž průnikem je jazyk, který
není bezkontextový.
Lx = {aibicj i, j ≥ 0} (počet a je stejný jako počet b)
Ly = {aibkck i, j ≥ 0} (počet b je stejný jako počet c)
Průnikem těchto jazyků je
L = Lx ∩ Ly = anbncn n ≥ 0 /∈ L (CF)
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Průnik
Věta
Třída bezkontextových jazyků není uzavřena vzhledem k operaci
průniku.
Důkaz:
Najdeme dva bezkontextové jazyky, jejichž průnikem je jazyk, který
není bezkontextový.
Lx = {aibicj i, j ≥ 0} (počet a je stejný jako počet b)
Ly = {aibkck i, j ≥ 0} (počet b je stejný jako počet c)
Průnikem těchto jazyků je
L = Lx ∩ Ly = anbncn n ≥ 0 /∈ L (CF)
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Doplněk (komplement)
Věta
Třída bezkontextových jazyků není uzavřena vzhledem k operaci
doplňku (komplementu) nad danou abecedou.
Důkaz sporem:
Podle DeMorganových pravidel platí L1 ∩ L2 = L1 ∪ L2
předpokládejme, že třída bezkontextových jazyků je uzavřena
vzhledem k operaci doplňku
⇒ na pravé straně rovnice je množina bezkontextových jazyků
⇒ na levé straně rovnice je množina, ve které existují i jazyky,
které nejsou bezkontextové (průnikem dvou bezkontextových
jazyků může být i jazyk, který není bezkontextový)
⇒ spor
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Doplněk (komplement)
Věta
Třída bezkontextových jazyků není uzavřena vzhledem k operaci
doplňku (komplementu) nad danou abecedou.
Důkaz sporem:
Podle DeMorganových pravidel platí L1 ∩ L2 = L1 ∪ L2
předpokládejme, že třída bezkontextových jazyků je uzavřena
vzhledem k operaci doplňku
⇒ na pravé straně rovnice je množina bezkontextových jazyků
⇒ na levé straně rovnice je množina, ve které existují i jazyky,
které nejsou bezkontextové (průnikem dvou bezkontextových
jazyků může být i jazyk, který není bezkontextový)
⇒ spor
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Doplněk (komplement)
Věta
Třída bezkontextových jazyků není uzavřena vzhledem k operaci
doplňku (komplementu) nad danou abecedou.
Důkaz sporem:
Podle DeMorganových pravidel platí L1 ∩ L2 = L1 ∪ L2
předpokládejme, že třída bezkontextových jazyků je uzavřena
vzhledem k operaci doplňku
⇒ na pravé straně rovnice je množina bezkontextových jazyků
⇒ na levé straně rovnice je množina, ve které existují i jazyky,
které nejsou bezkontextové (průnikem dvou bezkontextových
jazyků může být i jazyk, který není bezkontextový)
⇒ spor
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Doplněk (komplement)
Věta
Třída bezkontextových jazyků není uzavřena vzhledem k operaci
doplňku (komplementu) nad danou abecedou.
Důkaz sporem:
Podle DeMorganových pravidel platí L1 ∩ L2 = L1 ∪ L2
předpokládejme, že třída bezkontextových jazyků je uzavřena
vzhledem k operaci doplňku
⇒ na pravé straně rovnice je množina bezkontextových jazyků
⇒ na levé straně rovnice je množina, ve které existují i jazyky,
které nejsou bezkontextové (průnikem dvou bezkontextových
jazyků může být i jazyk, který není bezkontextový)
⇒ spor
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Doplněk (komplement)
Věta
Třída bezkontextových jazyků není uzavřena vzhledem k operaci
doplňku (komplementu) nad danou abecedou.
Důkaz sporem:
Podle DeMorganových pravidel platí L1 ∩ L2 = L1 ∪ L2
předpokládejme, že třída bezkontextových jazyků je uzavřena
vzhledem k operaci doplňku
⇒ na pravé straně rovnice je množina bezkontextových jazyků
⇒ na levé straně rovnice je množina, ve které existují i jazyky,
které nejsou bezkontextové (průnikem dvou bezkontextových
jazyků může být i jazyk, který není bezkontextový)
⇒ spor
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Doplněk (komplement)
Věta
Třída bezkontextových jazyků není uzavřena vzhledem k operaci
doplňku (komplementu) nad danou abecedou.
Důkaz sporem:
Podle DeMorganových pravidel platí L1 ∩ L2 = L1 ∪ L2
předpokládejme, že třída bezkontextových jazyků je uzavřena
vzhledem k operaci doplňku
⇒ na pravé straně rovnice je množina bezkontextových jazyků
⇒ na levé straně rovnice je množina, ve které existují i jazyky,
které nejsou bezkontextové (průnikem dvou bezkontextových
jazyků může být i jazyk, který není bezkontextový)
⇒ spor
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Průnik s regulárním jazykem
Věta
Třída bezkontextových jazyků je uzavřena vzhledem k průniku
s regulárním jazykem.
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Důkaz:
A1 = (Q1, Σ1, Γ1, δ1, q
(1)
0 , Z
(1)
0 , F1)
A2 = (Q2, Σ2, δ2, q
(2)
0 , F2)
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Důkaz:
A1 = (Q1, Σ1, Γ1, δ1, q
(1)
0 , Z
(1)
0 , F1)
A2 = (Q2, Σ2, δ2, q
(2)
0 , F2)
Sestrojíme A = (Q, Σ, Γ, δ, q0, Z0, F), L(A) = L(A1) ∩ L(A2).
Výpočet v automatu A je simultánní simulací obou původních
automatů.
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Důkaz:
A1 = (Q1, Σ1, Γ1, δ1, q
(1)
0 , Z
(1)
0 , F1)
A2 = (Q2, Σ2, δ2, q
(2)
0 , F2)
Sestrojíme A = (Q, Σ, Γ, δ, q0, Z0, F), L(A) = L(A1) ∩ L(A2).
Výpočet v automatu A je simultánní simulací obou původních
automatů.
Σ = Σ1 ∪ Σ2, Γ = Γ1, Z0 = Z0
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Důkaz:
A1 = (Q1, Σ1, Γ1, δ1, q
(1)
0 , Z
(1)
0 , F1)
A2 = (Q2, Σ2, δ2, q
(2)
0 , F2)
Sestrojíme A = (Q, Σ, Γ, δ, q0, Z0, F), L(A) = L(A1) ∩ L(A2).
Výpočet v automatu A je simultánní simulací obou původních
automatů.
Σ = Σ1 ∪ Σ2, Γ = Γ1, Z0 = Z0
Stavy automatu A jsou uspořádané dvojice stavů původních
automatů.
Q = {[q1, q2] q1 ∈ Q1, q2 ∈ Q2}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Důkaz:
A1 = (Q1, Σ1, Γ1, δ1, q
(1)
0 , Z
(1)
0 , F1)
A2 = (Q2, Σ2, δ2, q
(2)
0 , F2)
Sestrojíme A = (Q, Σ, Γ, δ, q0, Z0, F), L(A) = L(A1) ∩ L(A2).
Výpočet v automatu A je simultánní simulací obou původních
automatů.
Σ = Σ1 ∪ Σ2, Γ = Γ1, Z0 = Z0
Stavy automatu A jsou uspořádané dvojice stavů původních
automatů.
Q = {[q1, q2] q1 ∈ Q1, q2 ∈ Q2}
Množina koncových stavů: F = {[q1, q2] q1 ∈ F1, q2 ∈ F2}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Důkaz:
A1 = (Q1, Σ1, Γ1, δ1, q
(1)
0 , Z
(1)
0 , F1)
A2 = (Q2, Σ2, δ2, q
(2)
0 , F2)
Definujeme δ funkci:
1 ∀a ∈ Σ, q1, p1 ∈ Q1, q2, p2 ∈ Q2, Z ∈ Γ, γ ∈ Γ∗
1:
δ([q1, q2], a, Z) ([p1, p2], γ)
⇐⇒
δ1(q1, a, Z) (p1, γ), δ2(q2, a) p2
2 Vyřešíme odlišnost původních automatů při práci se vstupní
abecedou – ε-kroky pro konečný automat:
∀q1, p1 ∈ Q1, q2 ∈ Q2, Z ∈ Γ, γ ∈ Γ∗
1:
δ([q1, q2], ε, Z) ([p1, q2], γ) ⇐⇒ δ1(q1, ε, Z) (p1, γ)
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Důkaz:
A1 = (Q1, Σ1, Γ1, δ1, q
(1)
0 , Z
(1)
0 , F1)
A2 = (Q2, Σ2, δ2, q
(2)
0 , F2)
Definujeme δ funkci:
1 ∀a ∈ Σ, q1, p1 ∈ Q1, q2, p2 ∈ Q2, Z ∈ Γ, γ ∈ Γ∗
1:
δ([q1, q2], a, Z) ([p1, p2], γ)
⇐⇒
δ1(q1, a, Z) (p1, γ), δ2(q2, a) p2
2 Vyřešíme odlišnost původních automatů při práci se vstupní
abecedou – ε-kroky pro konečný automat:
∀q1, p1 ∈ Q1, q2 ∈ Q2, Z ∈ Γ, γ ∈ Γ∗
1:
δ([q1, q2], ε, Z) ([p1, q2], γ) ⇐⇒ δ1(q1, ε, Z) (p1, γ)
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Důkaz:
A1 = (Q1, Σ1, Γ1, δ1, q
(1)
0 , Z
(1)
0 , F1)
A2 = (Q2, Σ2, δ2, q
(2)
0 , F2)
Definujeme δ funkci:
1 ∀a ∈ Σ, q1, p1 ∈ Q1, q2, p2 ∈ Q2, Z ∈ Γ, γ ∈ Γ∗
1:
δ([q1, q2], a, Z) ([p1, p2], γ)
⇐⇒
δ1(q1, a, Z) (p1, γ), δ2(q2, a) p2
2 Vyřešíme odlišnost původních automatů při práci se vstupní
abecedou – ε-kroky pro konečný automat:
∀q1, p1 ∈ Q1, q2 ∈ Q2, Z ∈ Γ, γ ∈ Γ∗
1:
δ([q1, q2], ε, Z) ([p1, q2], γ) ⇐⇒ δ1(q1, ε, Z) (p1, γ)
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
L = wwR w ∈ {a, b}∗ , R = a∗
L ∩ R = anan n ≥ 0 = a2n n ≥ 0
Sestrojíme automaty A1, L(A1) = L, A2, L(A2) = R:
A1 = ({q0, q1, q2}, {a, b}, {Z0, a, b}, δ1, q0, Z0, {q2}), kde
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
A2 = ({r} {a}, δ2, r, {r}), kde δ2(r, a) = r
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
L = wwR w ∈ {a, b}∗ , R = a∗
L ∩ R = anan n ≥ 0 = a2n n ≥ 0
Sestrojíme automaty A1, L(A1) = L, A2, L(A2) = R:
A1 = ({q0, q1, q2}, {a, b}, {Z0, a, b}, δ1, q0, Z0, {q2}), kde
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
A2 = ({r} {a}, δ2, r, {r}), kde δ2(r, a) = r
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
L = wwR w ∈ {a, b}∗ , R = a∗
L ∩ R = anan n ≥ 0 = a2n n ≥ 0
Sestrojíme automaty A1, L(A1) = L, A2, L(A2) = R:
A1 = ({q0, q1, q2}, {a, b}, {Z0, a, b}, δ1, q0, Z0, {q2}), kde
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
A2 = ({r} {a}, δ2, r, {r}), kde δ2(r, a) = r
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
L = wwR w ∈ {a, b}∗ , R = a∗
L ∩ R = anan n ≥ 0 = a2n n ≥ 0
Sestrojíme automaty A1, L(A1) = L, A2, L(A2) = R:
A1 = ({q0, q1, q2}, {a, b}, {Z0, a, b}, δ1, q0, Z0, {q2}), kde
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
A2 = ({r} {a}, δ2, r, {r}), kde δ2(r, a) = r
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
L = wwR w ∈ {a, b}∗ , R = a∗
L ∩ R = anan n ≥ 0 = a2n n ≥ 0
Vytvoříme A = (Q, {a, b}, {Z0, a, b}, δ, [q0, r], Z0, F).
δ([q0, r], a, Z0) = {[q0, r], aZ0])}
δ([q0, r], a, a) = {([q0, r], aa), ([q1, r], ε)}
δ([q1, r], a, a) = {[q1, r], ε)}
δ([q1, r], ε, Z0) = {([q2, r], ε)}
Q = {[q0, r], [q1, r], [q2, r]}, F = {[q2, r]}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
L = wwR w ∈ {a, b}∗ , R = a∗
L ∩ R = anan n ≥ 0 = a2n n ≥ 0
Vytvoříme A = (Q, {a, b}, {Z0, a, b}, δ, [q0, r], Z0, F).
δ([q0, r], a, Z0) = {[q0, r], aZ0])}
δ([q0, r], a, a) = {([q0, r], aa), ([q1, r], ε)}
δ([q1, r], a, a) = {[q1, r], ε)}
δ([q1, r], ε, Z0) = {([q2, r], ε)}
Q = {[q0, r], [q1, r], [q2, r]}, F = {[q2, r]}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
L = wwR w ∈ {a, b}∗ , R = a∗
L ∩ R = anan n ≥ 0 = a2n n ≥ 0
Vytvoříme A = (Q, {a, b}, {Z0, a, b}, δ, [q0, r], Z0, F).
δ([q0, r], a, Z0) = {[q0, r], aZ0])}
δ([q0, r], a, a) = {([q0, r], aa), ([q1, r], ε)}
δ([q1, r], a, a) = {[q1, r], ε)}
δ([q1, r], ε, Z0) = {([q2, r], ε)}
Q = {[q0, r], [q1, r], [q2, r]}, F = {[q2, r]}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
L = wwR w ∈ {a, b}∗ , R = a∗
L ∩ R = anan n ≥ 0 = a2n n ≥ 0
Vytvoříme A = (Q, {a, b}, {Z0, a, b}, δ, [q0, r], Z0, F).
δ([q0, r], a, Z0) = {[q0, r], aZ0])}
δ([q0, r], a, a) = {([q0, r], aa), ([q1, r], ε)}
δ([q1, r], a, a) = {[q1, r], ε)}
δ([q1, r], ε, Z0) = {([q2, r], ε)}
Q = {[q0, r], [q1, r], [q2, r]}, F = {[q2, r]}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
L = wwR w ∈ {a, b}∗ , R = a∗ab∗a∗
L ∩ R = wwR w ∈ a∗ab∗
A1 = ({q0, q1, q2}, {a, b}, {Z0, a, b}, δ1, q0, Z0, {q2})
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
A2 = ({r, s, t}, {a, b}, δ2, r, {s, t})
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}


r
a
a




s
a
b




t
a
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
L = wwR w ∈ {a, b}∗ , R = a∗ab∗a∗
L ∩ R = wwR w ∈ a∗ab∗
A1 = ({q0, q1, q2}, {a, b}, {Z0, a, b}, δ1, q0, Z0, {q2})
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
A2 = ({r, s, t}, {a, b}, δ2, r, {s, t})
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}


r
a
a




s
a
b




t
a
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
L = wwR w ∈ {a, b}∗ , R = a∗ab∗a∗
L ∩ R = wwR w ∈ a∗ab∗
A1 = ({q0, q1, q2}, {a, b}, {Z0, a, b}, δ1, q0, Z0, {q2})
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
A2 = ({r, s, t}, {a, b}, δ2, r, {s, t})
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}


r
a
a




s
a
b




t
a
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
L = wwR w ∈ {a, b}∗ , R = a∗ab∗a∗
L ∩ R = wwR w ∈ a∗ab∗
A1 = ({q0, q1, q2}, {a, b}, {Z0, a, b}, δ1, q0, Z0, {q2})
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
A2 = ({r, s, t}, {a, b}, δ2, r, {s, t})
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}


r
a
a




s
a
b




t
a
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}
δ([q0, r], a, Z0) = {([q0, r], aZ0), ([q0, s], aZ0)}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}
δ([q0, r], a, Z0) = {([q0, r], aZ0), ([q0, s], aZ0)}
δ([q0, s], a, Z0) = {([q0, t], aZ0)}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}
δ([q0, r], a, Z0) = {([q0, r], aZ0), ([q0, s], aZ0)}
δ([q0, s], a, Z0) = {([q0, t], aZ0)}
δ([q0, t], a, Z0) = {([q0, t], aZ0)}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}
δ([q0, r], a, a) = {([q0, r], aa), ([q0, s], aa), ([q1, r], ε), ([q1, s], ε)}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}
δ([q0, r], a, a) = {([q0, r], aa), ([q0, s], aa), ([q1, r], ε), ([q1, s], ε)}
δ([q0, s], a, a) = {([q0, t], aa), ([q1, t], ε)}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}
δ([q0, r], a, a) = {([q0, r], aa), ([q0, s], aa), ([q1, r], ε), ([q1, s], ε)}
δ([q0, s], a, a) = {([q0, t], aa), ([q1, t], ε)}
δ([q0, t], a, a) = {([q0, t], aa), ([q1, t], ε)}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}
δ([q0, r], a, b) = {([q0, r], ab), ([q0, s], ab)}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}
δ([q0, r], a, b) = {([q0, r], ab), ([q0, s], ab)}
δ([q0, s], a, b) = {([q0, t], ab)}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}
δ([q0, r], a, b) = {([q0, r], ab), ([q0, s], ab)}
δ([q0, s], a, b) = {([q0, t], ab)}
δ([q0, t], a, b) = {([q0, t], ab)}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}
δ([q0, s], b, Z0) = {([q0, s], bZ0)}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}
δ([q0, s], b, a) = {([q0, s], ba)}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}
δ([q0, s], b, b) = {([q0, s], bb), ([q1, s], ε)}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}
δ([q1, r], a, a) = {([q1, r], ε), ([q1, s], ε)}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}
δ([q1, r], a, a) = {([q1, r], ε), ([q1, s], ε)}
δ([q1, s], a, a) = {([q1, t], ε)}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}
δ([q1, r], a, a) = {([q1, r], ε), ([q1, s], ε)}
δ([q1, s], a, a) = {([q1, t], ε)}
δ([q1, t], a, a) = {([q1, t], ε)}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}
δ([q1, s], b, b) = {([q1, s], ε)}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}
δ([q1, r], ε, Z0) = {([q2, r], ε)}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}
δ([q1, r], ε, Z0) = {([q2, r], ε)}
δ([q1, s], ε, Z0) = {([q2, s], ε)}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
δ1(q0, a, Z0) = {(q0, aZ0)}
δ1(q0, a, a) = {(q0, aa), (q1, ε)}
δ1(q0, a, b) = {(q0, ab)}
δ1(q0, b, Z0) = {(q0, bZ0)}
δ1(q0, b, a) = {(q0, ba)}
δ1(q0, b, b) = {(q0, bb), (q1, ε)}
δ1(q1, a, a) = {(q1, ε)}
δ1(q1, b, b) = {(q1, ε)}
δ1(q1, ε, Z0) = {(q2, ε)}
δ2(r, a) = {r, s}
δ2(s, a) = {t}
δ2(s, b) = {s}
δ2(t, a) = {t}
δ([q1, r], ε, Z0) = {([q2, r], ε)}
δ([q1, s], ε, Z0) = {([q2, s], ε)}
δ([q1, t], ε, Z0) = {([q2, t], ε)}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
Celá δ-funkce:
δ([q0, r], a, Z0) = {([q0, r], aZ0), ([q0, s], aZ0)}
δ([q0, s], a, Z0) = {([q0, t], aZ0)}
δ([q0, t], a, Z0) = {([q0, t], aZ0)}
δ([q0, r], a, a) = {([q0, r], aa), ([q0, s], aa), ([q1, r], ε), ([q1, s], ε)}
δ([q0, s], a, a) = {([q0, t], aa), ([q1, t], ε)}
δ([q0, t], a, a) = {([q0, t], aa), ([q1, t], ε)}
δ([q0, r], a, b) = {([q0, r], ab), ([q0, s], ab)}
δ([q0, s], a, b) = {([q0, t], ab)}
δ([q0, t], a, b) = {([q0, t], ab)}
δ([q0, s], b, Z0) = {([q0, s], bZ0)}
δ([q0, s], b, a) = {([q0, s], ba)}
δ([q0, s], b, b) = {([q0, s], bb), ([q1, s], ε)}
δ([q1, r], a, a) = {([q1, r], ε), ([q1, s], ε)}
δ([q1, s], a, a) = {([q1, t], ε)}
δ([q1, t], a, a) = {([q1, t], ε)}
δ([q1, s], b, b) = {([q1, s], ε)}
δ([q1, r], ε, Z0) = {([q2, r], ε)}
δ([q1, s], ε, Z0) = {([q2, s], ε)}
δ([q1, t], ε, Z0) = {([q2, t], ε)}
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Uzávěrové vlastnosti jako kritérium bezkontextovosti
Použití – je jazyk L1 bezkontextový?
pokud dokážeme L1 přepsat na sjednocení bezkontextových
jazyků, je L1 bezkontextový (totéž pro zřetězení, iteraci,
pozitivní iteraci, reverzi, substituci, průnik s reg. jazykem)
pokud L1 sjednotíme s bezkontextovým jazykem a dostaneme
jazyk, o němž víme, že není bezkontextový, pak ani L1 není
bezkontextový (totéž pro zřetězení, iteraci, pozitivní iteraci,
reverzi, substituci, průnik s reg. jazykem)
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Uzávěrové vlastnosti jako kritérium bezkontextovosti
Použití – je jazyk L1 bezkontextový?
pokud dokážeme L1 přepsat na sjednocení bezkontextových
jazyků, je L1 bezkontextový (totéž pro zřetězení, iteraci,
pozitivní iteraci, reverzi, substituci, průnik s reg. jazykem)
pokud L1 sjednotíme s bezkontextovým jazykem a dostaneme
jazyk, o němž víme, že není bezkontextový, pak ani L1 není
bezkontextový (totéž pro zřetězení, iteraci, pozitivní iteraci,
reverzi, substituci, průnik s reg. jazykem)
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Uzávěrové vlastnosti jako kritérium bezkontextovosti
Použití – je jazyk L1 bezkontextový?
Pozor – sjednocením dvou jazyků, z jichž některý není
bezkontextový, může vzniknout bezkontextový jazyk:
L1 = {anbncn n ≥ 1} /∈ L (CF)
L2 = {aibjci i, j ≥ 1} ∈ L (CF)
L1 ∪ L2 = L2
Proč? Implikace!
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Uzávěrové vlastnosti jako kritérium bezkontextovosti
Použití – je jazyk L1 bezkontextový?
Pozor – sjednocením dvou jazyků, z jichž některý není
bezkontextový, může vzniknout bezkontextový jazyk:
L1 = {anbncn n ≥ 1} /∈ L (CF)
L2 = {aibjci i, j ≥ 1} ∈ L (CF)
L1 ∪ L2 = L2
Proč? Implikace!
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
Zjistíme, zda je následující jazyk bezkontextový:
L = an1 bn1 an2 bn2 . . . ank bnk k ≥ 0, ni ≥ 1, 1 ≤ i ≤ k
Víme, že jazyk L1 = anbn n ≥ 1 je bezkontextový, a je zřejmé,
že L = L∗
1 a proto i jazyk L je bezkontextový.
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
Kdy nelze použít jako kritérium bezkontextovosti:
Víme, že jazyk L = an2
n ≥ 0 není bezkontextový. Zvolíme
následující bezkontextovou (dokonce regulární) substituci:
s(a) = b∗
Po uplatnění substituce dostaneme jazyk bi i ≥ 0 , což je
bezkontextový (dokonce regulární) jazyk. Proto není pravda, že
když je výsledkem operace bezkontextový jazyk, tak by operandy
operace měly být také.
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
L = w ∈ {a, b, c}∗ |w|a = |w|b = |w|c
Předpokládejme, že jazyk L je bezkontextový. Pak by
průnikem tohoto jazyka s jakýmkoliv regulárním jazykem byl
také bezkontextový jazyk.
Vezmeme regulární jazyk R = a∗b∗c∗
Průnikem je:
L ∩ R = anbncn n ≥ 0
O tomto jazyce víme, že není bezkontextový, proto L /∈ L (CF).
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
L = w ∈ {a, b, c}∗ |w|a = |w|b = |w|c
Předpokládejme, že jazyk L je bezkontextový. Pak by
průnikem tohoto jazyka s jakýmkoliv regulárním jazykem byl
také bezkontextový jazyk.
Vezmeme regulární jazyk R = a∗b∗c∗
Průnikem je:
L ∩ R = anbncn n ≥ 0
O tomto jazyce víme, že není bezkontextový, proto L /∈ L (CF).
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
L = w ∈ {a, b, c}∗ |w|a = |w|b = |w|c
Předpokládejme, že jazyk L je bezkontextový. Pak by
průnikem tohoto jazyka s jakýmkoliv regulárním jazykem byl
také bezkontextový jazyk.
Vezmeme regulární jazyk R = a∗b∗c∗
Průnikem je:
L ∩ R = anbncn n ≥ 0
O tomto jazyce víme, že není bezkontextový, proto L /∈ L (CF).
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
L = w ∈ {a, b, c}∗ |w|a = |w|b = |w|c
Předpokládejme, že jazyk L je bezkontextový. Pak by
průnikem tohoto jazyka s jakýmkoliv regulárním jazykem byl
také bezkontextový jazyk.
Vezmeme regulární jazyk R = a∗b∗c∗
Průnikem je:
L ∩ R = anbncn n ≥ 0
O tomto jazyce víme, že není bezkontextový, proto L /∈ L (CF).
Vztah k REG Sjednocení Zřetězení Iterace Zrcadlení Substituce Průnik Doplněk Průnik s REG Kritérium bezkontextovosti
Příklad
L = w ∈ {a, b, c}∗ |w|a = |w|b = |w|c
Předpokládejme, že jazyk L je bezkontextový. Pak by
průnikem tohoto jazyka s jakýmkoliv regulárním jazykem byl
také bezkontextový jazyk.
Vezmeme regulární jazyk R = a∗b∗c∗
Průnikem je:
L ∩ R = anbncn n ≥ 0
O tomto jazyce víme, že není bezkontextový, proto L /∈ L (CF).