Turing-g´epek Logika ´es sz´ am´ıt´ aselm´elet, 7. gyakorlat
2009/10 II. f´el´ev
Sz´ am´ıt´ aselm´ elet (7. gyakorlat)
Turing-g´ epek
2009/10 II. f´ el´ ev
1 / 1
A Turing-g´ep Az algoritmus fogalm´anak egy intuit´ıv defin´ıci´oja: Utas´ıt´asok egy j´ oldefini´alt, v´eges sorozata, melyeket v´egrehajtva megoldhat´ o egy adott oz¨ ul feladat (probl´ema). Az algoritmus fogalm´anak matematikai modelljei k¨ az egyik leggyakrabban haszn´alt a Turing g´ep. Turing-g´ep A Turing-g´ep egy olyan M = hQ, Σ, Γ, δ, q0 , qi , qn i rendszer, ahol • Q az ´ allapotok v´eges, nem¨ ures halmaza, • q0 , qi , qn ∈ Q, q0 a kezd˝ o- qi az elfogad´o ´es qn az elutas´ıt´ o ´allapot, • Σ´ es Γ ´ab´ec´ek, a bemen˝o jelek illetve a szalagszimb´ olumok ´ab´ec´eje
u ´gy, hogy Σ ⊆ Γ ´es Γ \ Σ tartalmaz egy speci´alis t szimb´ olumot, • δ : (Q \ {qi , qn }) × Γ → Q × Γ × {L, S, R} az ´ atmenet f¨ uggv´eny.
Sz´ am´ıt´ aselm´ elet (7. gyakorlat)
Turing-g´ epek
2009/10 II. f´ el´ ev
2 / 1
Konfigur´ aci´ o, konfigur´aci´o´atmenet A Turing-g´ep m˝ uk¨ od´es´enek f´azisait a g´ep konfigur´aci´ oival ´ırjuk le. A Turing-g´ep konfigur´aci´oja egy uqv sz´o, ahol q ∈ Q ´es u, v ∈ Γ∗ , v 6= ε. Ez a konfigur´aci´ o a g´ep azon ´allapot´at t¨ ukr¨ozi amikor a szalag tartalma uv (uv el˝ ott ´es ut´an a szalagon m´ar csak t van), a g´ep a q ´allapotban van, ´es a g´ep ´ır´ o-olvas´ o feje a v sz´o els˝o bet˝ uj´ere mutat. A g´ep kezd˝okonfigur´aci´ oja egy olyan q0 u sz´o, ahol u csak Σ-beli bet˝ uket tartalmaz. Egy Turing-g´ep konfigur´aci´o´atmenet´et az al´abbiak szerint defini´aljuk. Legyen uqav egy konfigur´aci´o, ahol a ∈ Γ, u, v ∈ Γ∗ . • Ha δ(q, a) = (r , b, R), akkor uqav ` ubrv 0 , ahol v 0 = v , ha v 6= ε,
k¨ ul¨ onben v 0 = t, • ha δ(q, a) = (r , b, S), akkor uqav ` urbv , • ha δ(q, a) = (r , b, L), akkor uqav ` u 0 rcbv , ahol c ∈ Γ ´ es u 0 c = u, ha
u 6= ε, k¨ ul¨ onben u 0 = u ´es c = t. Sz´ am´ıt´ aselm´ elet (7. gyakorlat)
Turing-g´ epek
2009/10 II. f´ el´ ev
3 / 1
Turing-g´ep ´ altal felismert nyelv
Azt mondjuk, hogy M v´eges sok l´ep´esben eljut a C konfigur´aci´ ob´ ol a C 0 konfigur´aci´ oba (jele C `∗ C 0 ), ha van olyan n ≥ 0 ´es C1 , . . . , Cn konfigur´aci´ oso- rozat, hogy C1 = C , Cn = C 0 ´es minden 1 ≤ i ≤ n-re, Ci ` Ci+1 . Ha q ∈ {qi , qn }, akkor azt mondjuk, hogy az uqv konfigur´aci´ o egy meg´all´asi konfigur´aci´o. q = qi eset´eben elfogad´ o, m´ıg q = qn eset´eben elutas´ıt´ o konfigur´aci´or´ol besz´el¨ unk. Az M ´altal felismert nyelv (amit L(M)-mel jel¨ ol¨ unk) azoknak az u ∈ Σ∗ szavaknak a halmaza, melyekre igaz, hogy q0 u `∗ xqi y valamely x, y ∈ Γ∗ , y 6= ε szavakra.
Sz´ am´ıt´ aselm´ elet (7. gyakorlat)
Turing-g´ epek
2009/10 II. f´ el´ ev
4 / 1
Turing-felismerhet˝ o ´es eld¨onthet˝o nyelvek, id˝oig´eny Egy L ⊆ Σ∗ nyelv Turing-felismerhet˝o, ha L = L(M) valamely M Turing-g´epre. Tov´abb´a, egy L ⊆ Σ∗ nyelv eld¨onthet˝ o, ha l´etezik olyan M Turing-g´ep, mely minden bemeneten meg´all´asi konfigur´aci´ oba jut ´es felismeri az L-et. A Turing-felismerhet˝o nyelveket szok´as rekurz´ıvan felsorolhat´ onak, az eld¨ onthet˝ o nyelveket pedig rekurz´ıvnak is nevezni. A rekurz´ıvan felsorolhat´ o nyelvek oszt´aly´at RE -vel, a rekurz´ıv nyelvek oszt´aly´at pedig R-rel jel¨ olj¨ uk. Tekints¨ unk egy M = hQ, Σ, Γ, δ, q0 , qi , qn i Turing-g´epet ´es annak egy u ∈ Σ∗ bemen˝szav´at. Azt mondjuk, hogy M fut´asi ideje (id˝ oig´enye) az u sz´ on n n ≥ 0, ha M a q0 u kezd˝okonfigur´aci´ob´ ol n l´ep´esben el tud jutni egy meg´all´asi konfigur´aci´oba. Ha nincs ilyen sz´am, akkor M fut´asi ideje az u-n v´egtelen. Legyen f : N → N egy f¨ uggv´eny. Azt mondjuk, hogy M id˝ oig´enye f (n) (vagy, hogy M egy f (n) id˝okorl´atos g´ep), ha minden u ∈ Σ∗ input sz´ ora, M id˝ oig´enye az u sz´on legfeljebb f (`(u)). Sz´ am´ıt´ aselm´ elet (7. gyakorlat)
Turing-g´ epek
2009/10 II. f´ el´ ev
5 / 1
T¨obbszalagos Turing-g´ep
k-szalagos Turing-g´ep A Turing-g´ep egy olyan M = hQ, Σ, Γ, δ, q0 , qi , qn i rendszer, ahol • Q az ´ allapotok v´eges, nem¨ ures halmaza, • q0 , qi , qn ∈ Q, q0 a kezd˝ o- qi az elfogad´o ´es qn az elutas´ıt´ o ´allapot, • Σ´ es Γ ´ab´ec´ek, a bemen˝o jelek illetve a szalagszimb´ olumok ´ab´ec´eje
u ´gy, hogy Σ ⊆ Γ ´es Γ \ Σ tartalmaz egy speci´alis t szimb´ olumot, • δ : (Q \ {qi , qn }) × Γk → Q × Γk × {L, S, R}k az ´ atmenet f¨ uggv´eny.
u1 v1 A k szalagos Turing-g´ep konfigur´aci´oja egy ... q ... sz´ o, ahol q ∈ Q uk vk ´es ui , vi ∈ Γ∗ , vi 6= ε (1 ≤ i ≤ k).
Sz´ am´ıt´ aselm´ elet (7. gyakorlat)
Turing-g´ epek
2009/10 II. f´ el´ ev
6 / 1
Sz´of¨ uggv´enyt kisz´am´ıt´o Turing-g´ep
Az M Turing-g´ep kisz´am´ıtja az f : Σ∗ → Γ∗ ∪ {%} sz´ of¨ uggv´enyt, ha M pontosan akkor jut meg´all´asi konfigur´aci´oba a kezd˝ okonfigur´aci´ ob´ ol, ha f (u) 6=% ´es a meg´all´asi konfigur´aci´o vqw , ahol q ∈ {qi , qn } ´es vw = f (u). (Nem l´enyeges, hogy qi -be vagy qn -be jut.)
Sz´ am´ıt´ aselm´ elet (7. gyakorlat)
Turing-g´ epek
2009/10 II. f´ el´ ev
7 / 1
Feladatok 1. Feladat: K´esz´ıts¨ unk TG-et, mely a 7-tel oszthat´ o hossz´ us´ag´ u szavak nyelv´et ismeri fel! t/t, R
q6
t/t, R
q5
q4
t/t, R
q0
,R
t /t
,R
t /t
qi
(t ∈ Σ)
t/t, R
q1
t/t, R
q2
t/t, R
q3
qn
2. Feladat: K´esz´ıts¨ unk TG-et, mely azon szavakat ismeri fel, melyeknek 3. ´es 6. bet˝ uje azonos! (Σ = {a, b})
q0
a/a,R b/b,R
q1
a/a,R b/b,R
a
R q3 , a /
q2 b/b
Sz´ am´ıt´ aselm´ elet (7. gyakorlat)
,R
q6
a/a,R b/b,R
a/a,R b/b,R
Turing-g´ epek
q4
q7
a/a,R b/b,R
a/a,R b/b,R
q5 a/a, R qi
qn
q8 b/b, R 2009/10 II. f´ el´ ev
8 / 1
Feladatok 3. Feladat: K´esz´ıts¨ unk TG-et, mely mindig meg´all, ´es meg´all´askor az input sz´ o olvashat´ o a szalagon, de egy cell´aval jobbra tolva! (Σ = {0, 1}) 0/0, R
q0
1/t ,R t/ R t, Sz´ am´ıt´ aselm´ elet (7. gyakorlat)
0/1, R
qS
t/ 0, 1/0, R
R , t 0/
q1
R
qi
qn
,R 1 / t
1/1, R
Turing-g´ epek
2009/10 II. f´ el´ ev
9 / 1
Feladatok
4. Feladat: K´esz´ıts¨ unk 2-szalagos TG-et, mely ´atm´asolja az inputot a 2. szalagra ´es a.) nem t¨orli b.) t¨orli az inputot az els˝ o szalagr´ ol! (Σ = {a, b}) a.)
a,t/t,a,R,R
a,t/a,a,R,R b,t/b,b,R,R
q0
t, t/t, t, S, S
Sz´ am´ıt´ aselm´ elet (7. gyakorlat)
b.) b,t/t,b,R,R qi
qn
Turing-g´ epek
q0
t, t/t, t, S, S
qi
2009/10 II. f´ el´ ev
qn
10 / 1
Feladatok 5. Feladat: K´esz´ıts¨ unk TG-et, mely az u 7→ uu sz´ of¨ uggv´enyt sz´amolja ki! (Σ = {a, b}) a/ˆ a,R a/a,R ˆ ˆ b,R ˆ b/b,R b/
ˆ a/a,R ˆ b/b,R
qi
t/t, S
,R a ¯ / a
q1
t/ ˆa, L
a/ˆ a,L a/a,L ˆ ˆ b,L ˆ b/b,L b/
¯a/a, R
q0
q3
¯ b/b, R
b/b¯ ,R
q2
qn
L , ˆ b t/
a/ˆ a,R a/a,R ˆ ˆ b,R ˆ b/b,R b/
Sz´ am´ıt´ aselm´ elet (7. gyakorlat)
Turing-g´ epek
2009/10 II. f´ el´ ev
11 / 1
Feladatok 6. Feladat: K´esz´ıts¨ unk TG-et, mely az L = {w #w −1 | w ∈ {a, b}∗ } a/a,R nyelvet ismeri fel! b/b,R #/#,R
qi
t/t, S
q6
#/#, R
qi
t/t, S
q1
t/t, R
q0 b/t
,R
t/t, L
q2
t/t, L
q3 a/t ,L
q4
,L t / b
q3
t/t, R
q2
t/t, L
a/t ,L
q5 q4
qn
,L t b/
a/a,R b/b,R #/#,R
q5
qn
a/a,L b/b,L
(L = {ww −1 | w ∈ {a, b}∗ })
a/a,R b/b,R Sz´ am´ıt´ aselm´ elet (7. gyakorlat)
q1
q0 b /t ,R
a/a,R b/b,R
,R t / a
,R t a/
t/t, L
a/a,L b/b,L #/#,L
Turing-g´ epek
2009/10 II. f´ el´ ev
12 / 1
Feladatok 7. Feladat: K´esz´ıts¨ unk TG-et, mely az L = {w #w | w ∈ {a, b}∗ } nyelvet ismeri fel! ¯ a/¯ a,R ¯ ¯ b/b,R
a/a,R b/b,R ¯ a/¯ a,R ¯ ¯ b/b,R
qi
t/t, S
q6
#/#, R
,R t a/
q1
#/#, R
q2
#/#, R
a/a,R b/b,R
Sz´ am´ıt´ aselm´ elet (7. gyakorlat)
a/¯a ,L
t/t, R
q0 b/t ,R
q3
Turing-g´ epek
¯ a/¯ a,L ¯ ¯ b/b,L a/a,L b/b,L #/#,L
q5 q4
qn
¯b, L / b
¯ a/¯ a,R ¯ b,R ¯ b/
2009/10 II. f´ el´ ev
13 / 1
Feladatok 8. Feladat: K´esz´ıts¨ unk TG-et, mely az L = {ww | w ∈ {a, b}∗ } nyelvet ismeri fel! t,a,a/t,a,a,S,L,R t,b,b/t,b,b,S,L,R
q3
,S ,L
,t
t/ t, t
,t
t/ t, t
q1
t,
t,
t, t,
q0
a,t,t/t,a,t,R,R,S b,t,t/t,b,t,R,R,S
t,t,a/t,t,a,S,S,L t,t,b/t,t,b,S,S,L
Sz´ am´ıt´ aselm´ elet (7. gyakorlat)
q2 ,S
,S ,R
,L ,S /t ,t ,t ,t t, t
q4
t, t, t/t, t, t, S, S, L
a,t,t/t,t,a,L,S,R b,t,t/t,t,b,L,S,R
,S
q5
,R
qi
t, t, t/t, t, t, S, S, S
a,t,t/a,t,t,L,S,S b,t,t/b,t,t,L,S,S
qn
a,t,t/a,t,t,R,S,S b,t,t/b,t,t,R,S,S
Turing-g´ epek
2009/10 II. f´ el´ ev
14 / 1
