AUTOMATY A GRAMATIKY Pavel Surynek Univerzita Karlova v Praze Matematicko-fyzikální fakulta Katedra teoretické informatiky a matematické logiky
11 Kontextové uzávěrové vlastnosti Turingův stroj Rekurzivně spočetné jazyky Kódování, enumerace
Kontextové uzávěrové vlastnosti (1)
kontextové jazyky jsou uzavřené na konečná sjednocení
kontextové gramatiky G1=(VN1, VT, S1, P1) a G2=(VN2, VT, S2, P2), kde VN1 ∩ VN2 =∅ položme G = (VN1 ∪ VN2 ∪ {S’}, VT, S’, P1∪P2 ∪{S’ → S1|S2 })
S’ je nový neterminál
platí L(G) = L(G1) ∪ L(G2)
kontextové jazyky jsou uzavřené na konkatenaci
položme G = (VN1 ∪ VN2 ∪ {S’}, VT, S’, P1∪P2 ∪ {S’ → S1.S2 })
S’ je nový neterminál
ošetřit přepis původních počátečních symbolů na λ
platí L(G) = L(G1).L(G2)
kontextové jazyky jsou uzavřené na iteraci
položme G = (VN1 ∪ {S’, S’’}, VT, S’, P1∪ {S’ → λ | S’’, S’’ → S’’S1 | S1 })
S’, S’’ jsou nové neterminály
ošetřit přepis původních počátečních symbolů na λ
je třeba dávat pozor na výskyt počátečního neterminálu vpravo (u bezkontextových netřeba)
platí L(G) = L(G1)*
kontextové jazyky jsou uzavřené na zrcadlový obraz
položme G = (VN1, VT, S1, {vR → wR |v → w∊P1}) platí L(G) = L(G1)R
2 | Automaty a gramatiky 11
Pavel Surynek, 2015
Kontextové uzávěrové vlastnosti (2)
kontextové jazyky jsou uzavřené na kontextovou substituci
substituce f: X → 2Y* je kontextová substituce, jestliže f(x) je kontextový jazyk pro každé x∊X
máme Gx = (VNx, Y, Sx, Px), že f(x) = L(Gx) pro každé x∊X
VNx jsou po dvou disjunktní
mějme G = (VN, X, S, P), zajímá nás kontextovost f(L(G))
položíme G’ = (VN ∪ ⋃x∊X VNx ∪ X, Y, S, P ∪ ⋃x∊X Px ∪ {x → Sx |x ∊ X})
případně ošetříme přepis neterminálů jiných než S na λ
platí L(G’) = f(L(G))
kontextové jazyky jsou uzavřené na doplňky a konečné průniky
velmi hluboký výsledek (řešilo se asi 20 let)
věta Immerman–Szelepcsényi
3 | Automaty a gramatiky 11
Pavel Surynek, 2015
Turingův stroj (1)
Turingův stroj
automat, který může přepisovat pásku páska je potenciálně nekonečná
v konečném čase stroj použije její konečnou část
historická vsuvka
30. léta 20. století
konečná výpočetní zařízení, formalizace algoritmu a problému
osobnosti
Turingův stroj, λ-kalkulus, RAM (random access machine)
Turing, Kleene, Markov, Post, Church
Churchova hypotéza (metavěta)
všechna konečná výpočetní zařízení jsou ekvivalentní, tj. ekvivaletní Turingovu stroji
nedokázáno ani nevyvráceno
4 | Automaty a gramatiky 11
Pavel Surynek, 2015
Turingův stroj (2)
Turingův stroj formálně
T = (Q, X, δ, q0, b, F)
Q - konečná neprázdná množina stavů X - konečná neprázdná množina symbolů (abeceda) F⊆Q - množina přijímajících stavů δ: (Q-F)×X → Q×X×{-1, 0, +1}
páska
přechodová funkce pro stav a čtený symbol dává nový stav, symbol k zápisu a následující pozici na pásce v přijímajícím stavu výpočet končí
x∊X r/w
q∊Q
q0∊Q - počáteční stav b∊X - symbol pro prázdnou buňku na pásce
předpoklady
páska je směrem doprava nekonečná vstupní slovo je napsané na levém konci pásky
zprava doplněné symbolem b do nekonečna
počáteční pozice je na prvním písmenu vstupního slova
5 | Automaty a gramatiky 11
Pavel Surynek, 2015
Výpočet Turingova stroje (u,q,v)
(i)
v
(ii)
v = x.v’ pro x∊X, w = u, z = y.v’ a δ(q,x)=(p,y,0), nebo
b b
x
u
v’
(u,q,v) b b b
r/w
žádný posun
posun doprava
q∊Q
(iii) u= u’.x’, v = x.v’ pro x,x’∊X, w = u’, z = x’.y.v’ a δ(q,x)=(p,y,-1)
q∊Q
(ii) v = x.v’ pro x∊X, w = u.y, z = v’ a δ(q,x)=(p,y,+1), nebo
posun doleva
zapisujeme (u,q,v) ⊢T (w,p,z)
u.v je slovo na nejmenší souvislé části pásky obsahující symboly ≠ b a čtenou buňku u je část vlevo od aktuální čtené pozice (kromě) v je část vpravo od aktuální čtené pozice (včetně)
změna konfigurace (u,q,v) na (w,p,z), jestliže
b b b
r/w
trojice (u,q,v), kde u,v∊X* a q∊Q
v∊X*
b b u∊X*
konfigurace Turingova stroje
nutno ošetřit případy, kdy u=λ
změna konfigurace na konečně mnoho kroků (u,q,v) ⊢T* (w,p,z)
6 | Automaty a gramatiky 11
(w,p,z) b b
y
u
z = v’ b b b r/w
w
p∊Q Pavel Surynek, 2015
Varianty Turingova stroje
nedeterministický
δ: (Q-F)×X → 2Q×X×{-1, 0, +1}
δ: (Q-F)×Xk → Q×Xk×{-1, 0, +1}k
(Q-F)×Xk
x2∊X r/w
k. páska xk∊X
2Q×Xk×{-1, 0, +1}k
případně δ: → u nedeterministické varianty
r/w
q∊Q
vstupní slovo na první pásce změna konfigurace analogicky
multi-dimenzionální
2. páska ...
místo δ(q,x) = ... budeme mít δ(q,x) ∍ ...
vícepáskový (k pásek)
r/w
pojem změny konfigurace se upraví
x1∊X
přechodová funkce bude nedeterministická
1. páska
páska má několik rozměrů (například 2D, 3D)
pohyb je možný ve všech směrech
7 | Automaty a gramatiky 11
2D
q∊Q r/w
Pavel Surynek, 2015
Jazyky a Turingovy stroje
slovo w∊(X-{b})* je přijímáno Turingovým strojem T = (Q, X, δ, q0, b, F), jestliže (λ, q0,w) ⊢T* (u,f,v) pro u,v∊X* a f∊F někdy je vyžadováno smazání pásky, tj. (λ, q0,w) ⊢T* (λ,f,b) jazyk L(T) přijímaný Turingovým strojem T
L(T) = { w | w∊(X-{b})* ∧ (∃f∊F) (λ, q0,w) ⊢T* (u,f,v) }
jazyky přijímané Turingovými stroji jsou právě rekurzivně spočetné jazyky (typu 0) [recursively enumerable language]
platí s libovolnou variantou Turingova stroje (více pásek, více dimenzí, s nedeterminismem)
všechny varianty TS mají stejnou výpočetní sílu lze se omezit na jednopáskový deterministický
8 | Automaty a gramatiky 11
Pavel Surynek, 2015
Turingův stroj ⇒ gramatika
mějme deterministický jednopáskový TS T = (Q, X, δ, q0, b, F)
hledáme gramatiku G=(VN,X,S,P) (bez omezení), že L(G) = L(T)
G vygeneruje pásku s prostorem pro výpočet a kopii vstupního slova, simuluje výpočet T nad vygenerovanou páskou (páska obsahuje zracadlový obraz vstupu)
VN = { Xx | x∊X } ∪ { Qq | q∊Q } ∪ {S, I, B, E} I pomocný neterminál pro generování w∊X* a wR, B pro generování prostoru na simulované pásce, E pro mazání simulační pásky pravidla P nechť w = x1x2...xn zahájení S → I Q q0 B I → x I Xx | B pro x∊X generování slova w a jeho kopie wR B → Xb B |Xb generování volného prostoru
simulace výpočtu nad wR Xx Qq Xy → Xz Qp Xy když δ(q,x)=(p,z,0) Xx Qq Xy → Qp Xz Xy když δ(q,x)=(p,z,+1) Xx Qq Xy → Xz Xy Qp když δ(q,x)=(p,z,-1)
derivace: S ⇒G* ... x1x2...xn I XxnXxn-1...Xx1Qq0 B ⇒G x1x2...xn B XxnXxn-1...Xx1Qq0 B ⇒G* ... x1x2...xn Xb...Xb XxnXxn-1...Xx1Qq0 Xb...Xb ⇒G* ... x1x2...xn u Qf v pro u,v∊{Xx | x∊X}* a f∊F ⇒G x1x2...xn u E v ⇒G* ... x1x2...xn E v ⇒G* x1x2...xn E ⇒G* x1x2...xn
mazání pásky Qf → E pro f∊F
9 | Automaty a gramatiky 11
X E → E pro X∊VN
E X → E pro X∊VN
E→λ Pavel Surynek, 2015
Gramatika ⇒ Turingův stroj
mějme gramatiku (bez omezení) G=(VN,VT,S,P)
hledáme TS T = (Q, X, δ, q0, b, F), že L(T) = L(G)
pracné po technické stránce, ukážeme abstraktně
konstrukce, z nichž na vyšší úrovni sestavíme T TS T1, že L(T1) = {#u#v# | u,v∊X* ∧ u ⇒G v }, # ∉ VN∪VT
na všech možných místech v u je vyzkoušena aplikace všech pravidel G
TS T2, že L(T2) = { w | (∃n∊ℕ0) w = #u1#u2#...#un# ∧ u1,...,un∊(VN∪VT)* ∧ u1 ⇒G u2 ∧ u2 ⇒G u3 ∧ ... ∧ un-1 ⇒G un } T2 bude
založen na T1 TS T3 generující systematicky všechna slova nad VN∪VT∪{#} začínající #S#
T3 vstupní slovo přepíše na následující slovo
spojením T2 a T3 vznikne požadovaný TS T
10 | Automaty a gramatiky 11
vstup: z∊ VT* na volné místo na pásce zapiš w = #S# loop if w∊L(T2) then if w končí #z# then přijmi z w ← výsledek práce T3 nad w Pavel Surynek, 2015
Kódování, slova a čísla
kódování různých datových typů vysoké úrovně
na nižší úrovni jen řetězce nebo přirozená čísla
ASCII či Unicode řetězce jsou reprezentovány posloupností bitů, tj. slovy nad {0, 1} slova nad {0, 1} lze interpretovat jako přirozená čísla
13. binární řetězec 21. binární řetězec 37. binární řetězec
máme i-tý program (respektive i-tý Turingův stroj)
“program + bitmapové obrázky = počítačová hra”
obrázek → kódování jako binární řetězec → číslo máme pojem i-tého obrázku
Př.: 101 0101 00101
program je jen vhodně interpretovaný řetězec
máme pojem i-tého řetězce pro i∊ℕ
analogicky pro bitmapové obrázky
interpretace bn-1...b1b0 = ∑ bi2i + 2n , kde bi∊{0,1} pro i=0,1,...,n-1
máme i-tou hru
důkaz je posloupnost výrazů
i-tý důkaz
11 | Automaty a gramatiky 11
Pavel Surynek, 2015
Množiny konečné a nekonečné
konečná množina K počet
Př.: {a, b, c} je konečná množina kardinality 3
jejích prvků - kardinalita je číslo ∊ℕ0
neexistuje
vzájemně jednoznačné zobrazení mezi K a její vlastní podmnožinou Př.: ℕ je nekonečná
nekonečná množina N existuje vzájemně
jednoznačné zobrazení mezi N a její vlastní podmnožinou
spočetná množina S existuje vzájemně
jednoznačné zobrazení
mezi S a ℕ spočetné 12 | Automaty a gramatiky 11
množiny jsou nekonečné
1 ↔2 2 ↔4 3↔ 6 ...
Př.: celá čísla ℤ 0 ↔1 -i ↔ 2i i ↔ 2i+1 ... Pavel Surynek, 2015
Enumerace a jazyky (1)
enumerace množiny M je vzájemně jednoznačné zobrazení mezi M a ℕ
máme tedy enumeraci řetězců, programů, obrázků, ...
lze enumerovat jazyky na danou abecedou X (={0,1})?
nikoli
pro spor předpokládejme, že jazyky nad {0, 1} enumerovat lze
máme tedy pojem i-tého jazyka, označme jazyky Li pro i∊ℕ položme L = { w | w∊{0,1}* ∧ w je i-tý binární řetězec ⇒ w ∉Li}
L je nad {0, 1}, mělo by se tedy jednat o j-tý jazyk pro jisté j∊ℕ
uvažme j-tý binární řetězec v a otázku, zda v∊L když v∊L, pak v∉L podle definice L když v∉L, pak v∊L podle definice L
13 | Automaty a gramatiky 11
Pavel Surynek, 2015
Enumerace a jazyky (2)
byla použita diagonalizace
nová diagonála nemůže být řádkem s každým řádkem se v jedné buňce liší
předpoklad, že jazyky nad {0,1} lze enumerovat, byl chybný
5
1
0
1 1 10 0
překlopíme hodnoty na diagonále
řetězce 2 3 4
2
jazyky
3
1
...
10 01
4 5
01 10
...
máme více jazyků než programů (Turingových strojů)
existují jazyky, pro které nemáme program (Turingův stroj), který je přijímá
nikoli všechny jazyky jsou rekurzivně spočetné
nekonstruktivní přístup
jak takový jazyk vypadá?
14 | Automaty a gramatiky 11
Pavel Surynek, 2015
