tin ukol3 .pdf

File information


Original filename: tin-ukol3.pdf

This PDF 1.5 document has been generated by TeX / MiKTeX pdfTeX-1.40.12, and has been sent on pdf-archive.com on 13/12/2011 at 20:38, from IP address 89.103.x.x. The current document download page has been viewed 942 times.
File size: 168 KB (5 pages).
Privacy: public file


Download original PDF file


tin-ukol3.pdf (PDF, 168 KB)


Share on social networks



Link to this file download page



Document preview


´ uc
ˇen´ı technicke
´ v Brne
ˇ
Vysoke
ˇn´ıch technologi´ı
Fakulta informac

Teoretick´a informatika
Tˇret´ı u
´kol

2011

Jan Tr´avn´ıˇcek

1.
Tato u
´loha je ˇreˇsena Turingov´
ym strojem, kter´
y je zobrazen na obr´azku 1, kter´
y si m˚
uˇzeme rozdˇelit na
tˇri samostatn´e ˇc´
asti. Jednotliv´e ˇc´
asti jsou v obr´azku naznaˇceny pˇreruˇsovan´
ymi ˇcarami. V prvn´ı ˇc´asti se
prov´ad´ı pouze kontrola, zda je na vstupn´ı p´asce validn´ı vstup ve tvaru ∆A#B∆ω , kde A, B ∈ {0, 1}+ .
Ve druh´e ˇc´asti je vstup zarovn´
an tak, aby oba operandy byly zobrazeny na stejn´em poˇctu bit˚
u.
T´ımto si zjednoduˇs´ıme n´
asledn´e sˇc´ıt´
an´ı, kter´e m˚
uˇzeme prov´adˇet obecnˇeji a nemus´ıme tuto skuteˇcnost
oˇsetˇrovat pˇri samotn´em sˇc´ıt´
an´ı.
Ve tˇret´ı ˇc´asti je pak jiˇz provedeno pouze samotn´e sˇc´ıt´an´ı dvou bin´arn´ıch ˇc´ısel stejn´e d´elky. V´
ysledek
sˇc´ıt´an´ı je pak uloˇzen na p´
asce dle zad´
an´ı.

R

R

¬0,1

#

R
¬0,1,#

L
}



¬0,1

¬0,1,#

R #L

R

}

ΔRΔL

}

ΔLΔωL

}

Δ

ΔRΔSRLΔ0L#RR

#

ΔRΔλL

Δ

}
ΔRΔSRLΔLSRLΔ0
RΔλL
# R R0L L Δ RS
L
Δ
#
0,1
} ω S R L 0,1 } λ S R
L

Δ

L

0 0R S L 0L
Δ R Δ
#
0 λ 1 1R S L 0L
Δ R Δ
#
0 ω 1 λ 0
1 0RΔSRLΔ1L#
0 λ 1
0 1R S L 0L
1 ω
Δ R Δ
#
1 λ 0 0R S L 1L
Δ R Δ
#
1 1R S L 1L
Δ R Δ
#
Obr´
azek 1: Turing˚
uv stroj reprezentuj´ıc´ı sˇc´ıt´an´ı dvou bin´arn´ıch ˇc´ısel.

1

2.
Tˇr´ıdu jazyk˚
u pˇrij´ıman´
ych turingov´
ym strojem oznaˇcme LT S . Tˇr´ıdu jazyk˚
u pˇrij´ıman´
ych dvojz´
asobn´ıkov´
ym automatem oznaˇcme LDA . Jsou-li tyto dvˇe tˇr´ıdy jazyk˚
u ekvivalentn´ı, je tˇreba dok´azat obˇe
inkluze LT S ⊆ LDA a LDA ⊆ LT S .
• Prvn´ı inkluzi LT S ⊆ LDA dok´
aˇzeme algoritmem, kter´
y k turingovu stroji sestroj´ı odpov´ıdaj´ıc´ı
dvojz´asobn´ıkov´
y automat. Idea tohoto algoritmu je pops´ana slovnˇe.
– Zvolme Z0 = #. Bez ujmy na obecnosti m˚
uˇzeme prohl´asit, ˇze # ∈
/ Σ. Symbol # je tedy
dno z´
asobn´ıku.
– Vstup dvojz´
asobn´ıkov´eho automatu odpov´ıd´a ˇretˇezci w, kter´
y odpov´ıd´a ˇretˇezci neblankov´
ych symbol˚
u poˇc´
ateˇcn´ı konfigurace p´asky turingova stroje, kter´a je ve tvaru ∆w∆ω .
– Na prvn´ı z´
asobn´ık vloˇz´ıme symbol ∆. Vrchol prvn´ıho z´asobn´ıku odpov´ıd´a pozici hlavy
simulovan´eho turingova stroje.
– D´ale je tˇreba definovat operace, kter´e umoˇzn
ˇuje turing˚
uv stroj, tedy z´apis, posun doprava
a posun doleva.
– Pˇri posunu doprava je tˇreba rozliˇsovat tˇri moˇzn´e varianty, kter´e mohou nastat. Pokud je
na druh´em z´
asobn´ıku pouze symbol # (dno z´asobn´ıku) a vstup dvojp´askov´eho z´asobn´ıku
obsahuje jeˇstˇe nepr´
azdn´
y ˇretˇezec, pˇreˇcteme symbol z p´asky a uloˇz´ıme jej na vrchol prvn´ıho
z´asobn´ıku. Pokud je na druh´em z´asobn´ıku pouze symbol # a na vstupu automatu je jiˇz
pr´azdn´
y ˇretˇezec, vloˇz´ıme na vrchol prvn´ıho z´asobn´ıku symbol ∆. Pokud je na druh´em
z´asobn´ıku mimo symbol # jeˇstˇe jin´
y symbol, vezmeme symbol z vrcholu druh´eho z´asobn´ıku,
odebereme ho z druh´eho z´
asobn´ıku a uloˇz´ıme ho na vrchol prvn´ıho z´asobn´ıku.
– Pˇri posunu doleva se pˇreˇcte symbol z vrcholu prvn´ıho z´asobn´ıku a pˇresune se na druh´
y
z´asobn´ık. Pokud je na vrcholu prvn´ıho z´asobn´ıku symbol dna z´asobn´ıku #, pˇredstavuje to
situaci, kdy bˇeh odpov´ıdajic´ıho turingova stroje posunul ˇctec´ı hlavu doleva pˇred zaˇc´
atek
p´asky.
– Pˇri z´
apisu znaku na m´ısto ˇctec´ı hlavy (vrchol prvn´ıho z´asobn´ıku) je znak z vrcholu odebr´
an
a nahrazen nov´
ym zpˇet na vrchol prvn´ıho z´asobn´ıku.
– Pˇri simulaci TS pˇri pˇrechodu mezi stavy se znak z prvn´ıho z´asobn´ıku pˇreˇcte a vr´at´ı zpˇet.
– Pˇri ˇr´
adne formalizaci popsan´eho algoritmu pak nen´ı teˇzk´e uk´azat, ˇze v´
ysledn´
y dvojz´
asobn´ıkov´
y automat simuluje turing˚
uv stroj.
• Druhou inkluzi LDA ⊆ LT S dok´
aˇzeme slovn´ım popisem algoritmu simulace dvojz´asobn´ıkov´eho
automatu pomoc´ı turingova stroje.
– Pouˇzijeme tˇr´ıp´
askov´
y turingov´
y stroj, kde na prvn´ı p´asku poloˇzme vstupn´ı ˇretˇezec dvojz´asobn´ıkov´eho automat. Druhou a tˇret´ı p´asku budeme povaˇzovat za dva z´asobn´ıky. Jiˇz
bylo dok´
az´
ano, ˇze v´ıcep´
askov´e turingovy stroje nezvyˇzuj´ı s´ılu a tud´ıˇz jsou ekvivalentn´ı s
jednop´
askov´
ymi turingovy stroji.
– Druhou a tˇret´ı p´
asku, budeme pouˇz´ıvat tak, jak jsme zvykl´ı z pr´ace se z´asobn´ıky. Budeme tedy vˇzdy pracovat pouze s posledn´ım symbolem, kter´
y pˇredstavuje vrchol z´asobn´ıku.
Z´asobn´ıkov´e“ operace jistˇe lze prov´adˇet pomoc´ı turingova stroje.

– Pˇri ˇr´
adn´e formalizaci popsan´eho postupu m˚
uˇzeme dok´azat, ˇze dvojz´asobn´ıkov´
y automat
lze simulovat tˇr´ıp´
askov´
ym turingov´
ym strojem, tedy i jednop´askov´
ym turingov´
ym strojem.
• Tˇr´ıdy jazyk˚
u LT S a LDA jsou tedy ekvivalentn´ı, jak bylo dok´azano neform´aln´ım popisem obou
stran inkluze.

2

3.
1. Nerozhodnutelnost
• Redukc´ı z probl´emu zastaveni TS.
• Probl´em zastaven´ı lze charakterizovat jazykem HP = {<M >#<w>|M je TS takov´
y, ˇze
zastav´ı, je-li spuˇstˇen na ˇretˇezci w}.
• Probl´em, zda jazyk dan´eho TS obsahuje alespoˇ
n jedno slovo z jazyka L3 = {ww|w ∈

{a, b} }, lze charakterizovat jazykem P = {<M >|(L(M ) ∩ L3 ) 6= ∅}.
• Sestroj´ıme redukci σ : {0, 1, #}∗ → {a, b}∗ z jazyka HP na jazyk P .
• TS Mσ vyˇc´ıslujic´ı σ pˇriˇrad´ı kaˇzd´emu vstupu x ∈ {0, 1, #}∗ ˇretˇezec <Mx >, kde Mx je TS,
kter´
y na vstupu w ∈ {a, b}∗ pracuje tatko:
(a) Mx smaˇze ˇretˇezec w ze sv´eho vstupn´ı p´asky.
(b) Na vstupn´ı p´
asku zap´ıˇse ˇretˇezec x.
(c) Mx ovˇeˇr´ı, zda x m´
a strukturu x1 #x2 , kde x1 je k´od TS a x2 k´od jeho vstupu. Nem´
a-li
tuto strukturu, odm´ıtne.
(d) Mx odsimuluje na sv´e p´
asce bˇeh TS s k´odem x1 na ˇretˇezci s k´odem x2 . Vede-li simulace
k zastaven´ı, pˇrijme, jinak cykl´ı.
• Mσ lze zˇrejmˇe realizovat jako u
´pln´
y TS – jedn´a se o v´
ypis pˇredpˇripraven´
ych komponent TS
(body a, c, d) a o k´
od TS, tker´
y pˇrep´ıˇse zadan´
y ˇretˇezec x na p´asku (bod b).
• Pro jazyk TS Mx plat´ı:
– L(Mx ) = ∅ ⇔ (L(Mx ) ∩ L3 ) = ∅ ⇔ x nen´ı platnou instanc´ı probl´emu zastaven´ı nebo
pokud x = x1 #x2 a TS s k´odem x1 nezastav´ı na ˇretˇezci s k´odem x2 (x ∈
/ HP ).
– L(Mx ) = {a, b}∗ ⇔ (L(Mx ) ∩ L3 ) 6= ∅ ⇔ x = x1 #x2 a TS s k´odem x1 zastav´ı na ˇretˇezci
s k´
odem x2 ⇔ x ∈ HP .
ˇ asteˇcnou rozhodnutelnost nen´ı ze zad´an´ı tˇreba dokazovat.
2. C´

3

4.
Turingovu stroji M4 odpov´ıd´
a gramatika G4 = ({S, A, B}, {a, b}, P, S), kde P je koneˇcn´a mnoˇzina
pravidel definov´
an´
ych n´
asledovnˇe
P: S −→ a | aA
A −→ bB
B −→ bB | aS
Mˇejme ˇretˇezec w = abbbaabaa, pro kter´
y jistˇe plat´ı, ˇze w ∈ L(M4 ). Bˇeh stroje M4 pro tento ˇretˇezec
po t´e vypad´a n´
asledovnˇe pro poˇc´
ateˇcn´ı konfiguraci p´asky ∆w∆ω .
(0, ∆abbbaabaa∆ω , 1) ` (1, ∆abbbaabaa∆ω , 2) ` (2, ∆abbbaabaa∆ω , 3) `
(3, ∆abbbaabaa∆ω , 4) ` (3, ∆abbbaabaa∆ω , 5) ` (3, ∆abbbaabaa∆ω , 6) `
(1, ∆abbbaabaa∆ω , 7) ` (2, ∆abbbaabaa∆ω , 8) ` (3, ∆abbbaabaa∆ω , 9) `
(1, ∆abbbaabaa∆ω , 10) ` (2, ∆abbbaabaa∆ω , 11) ` (5, ∆abbbaabaa∆ω , 10) `
(6, ∆abbbaaba∆ω , 10) ` (5, ∆abbbaaba∆ω , 9) ` (6, ∆abbbaab∆ω , 9) `
(5, ∆abbbaab∆ω , 8) ` (6, ∆abbbaa∆ω , 8) ` (5, ∆abbbaa∆ω , 7) ` (6, ∆abbba∆ω , 7) `
(5, ∆abbba∆ω , 6) ` (6, ∆abbb∆ω , 6) ` (5, ∆abbb∆ω , 5) ` (6, ∆abb∆ω , 5) `
(5, ∆abb∆ω , 4) ` (6, ∆ab∆ω , 4) ` (5, ∆ab∆ω , 3) ` (6, ∆a∆ω , 3) `
(5, ∆a∆ω , 2) ` (6, ∆∆ω , 2) ` (5, ∆∆ω , 1) ` (7, ∆∆ω , 2) ` (8, ∆Y ∆ω , 2) ` (8, ∆Y ∆ω , 1)
Dan´e slovo w je generov´
ano gramatikou G4 n´asleduj´ıc´ı posloupnost´ı derivac´ı:
S ⇒ aA ⇒ abB ⇒ abbB ⇒ abbbB ⇒ abbbaS ⇒ abbbaaA ⇒ abbbaabB ⇒ abbbaabaA ⇒ abbbaabaa.

4


Document preview tin-ukol3.pdf - page 1/5

Document preview tin-ukol3.pdf - page 2/5
Document preview tin-ukol3.pdf - page 3/5
Document preview tin-ukol3.pdf - page 4/5
Document preview tin-ukol3.pdf - page 5/5

Related documents


tin ukol3
navstevni rad cs
du zadani0302
soilmod
01 desatero
voto vohoz cz podm nky

Link to this page


Permanent link

Use the permanent link to the download page to share your document on Facebook, Twitter, LinkedIn, or directly with a contact by e-Mail, Messenger, Whatsapp, Line..

Short link

Use the short link to share your document on Twitter or by text message (SMS)

HTML Code

Copy the following HTML code to share your document on a Website or Blog

QR Code

QR Code link to PDF file tin-ukol3.pdf