-
[ Pobierz całość w formacie PDF ]
wych, które zawierają conajmniej dwa wystąpienia tego samego symbolu.
Zadanie 4.32 Zdefiniuj maszynę Turinga, która startując z pustą taśmą wejściową gene-
ruje na taśmie wyjściowej kolejne leksykograficznie słowa nad alfabetem {0, 1} pooddzie-
lane symbolem *, tj. *0*1*00*01*10*11*000*001 itd.
Zadanie 4.33 Niech M oznacza deterministycznÄ… maszynÄ™ Turinga; y, z dowolne konfi-
guracje tej maszyny oraz y -’!M z oznacza, że konfiguracja z jest bezpoÅ›rednim nastÄ™p-
nikiem konfiguracji y w maszynie M. Pokaż, że
L = {y#zR : y -’!M z} jest jÄ™zykiem bezkontekstowym.
Uwaga. Język L jest bezkontekstowy także wtedy, gdy M jest niedeterministyczna.
Zadanie 4.34 Podaj maszynę Turinga M, która dla danej maszyny Turinga N wypisuje
wszystkie jej konfiguracje (M pracuje w nieskończoność).
Zadanie 4.35 Podaj maszynę Turinga M, która startując od konfiguracji q0w, gdzie w "
{a, b}" zatrzymuje się w konfiguracji qf bn, jeśli w = anbn oraz pętli się w nieskończoność
dla pozostałych słów w.
Zadanie 4.36 Podaj maszynę Turinga M, która wylicza konkatenację słów nad alfabetem
{a, b}, to znaczy startujÄ…c od konfiguracji q0w1#w2 gdzie w1, w2 " {a, b}" zatrzymuje siÄ™
w konfiguracji qf w1w2.
Zadanie 4.37 Podaj maszynę Turinga M, która startując od konfiguracji q0w gdzie w
oznacza zapis binarny liczby n zatrzymuje siÄ™ w konfiguracji qf v, gdzie v jest zapisem
binarnym liczby n + 1 .
Zadanie 4.38 Podaj maszynę Turinga M, która znajduje następnik leksykograficzny sło-
wa nad alfabetem {a, b}, to znaczy startujÄ…c od konfiguracji q0w dochodzi do konfiguracji
qf v, gdzie v jest słowem występującym bezpośrednio po słowie w w uporządkowaniu lek-
sykograficznym, np. dla w = aab, v = aba.
106 Rozdział 4. Maszyny Turinga
Zadanie 4.39 Funkcja Ackermanna jest zdefiniowana następująco :
ñø
y + 1 jeżeli x = 0
òø
A(x, y) = A(x - 1, 1) jeżeli x = 0 i y = 0
óø
A(x - 1, A(x, y - 1)) w pozostałych przypadkach
Oblicz A(4,1). Pokaż, że
y
Podaj maszynę Turinga, która oblicza funkcję Ackermanna.
4.6 Problemy grafowe
Czasami zamiast mówić, że maszyna Turinga akceptuje język będziemy mówili, że ma-
szyna rozpoznaje problem. W takim przypadku, na początku obliczenia na taśmie maszyny
znajduje się tak zwana instancja problemu (zwana też wejściem problemu). Zakładamy, że
obliczenie zatrzymuje się dla każdej instancji i po zatrzymaniu zwraca odpowiedz, która
najczęściej jest typu TAK lub NIE. Mówiąc dokładniej, instancje są słowami wejściowymi
maszyny i maszyna akceptuje zbiór instancji dla których odpowiedz jest TAK.
Dla przykładu pokażemy jak maszyna Turinga może rozpoznawać problemy grafowe;
na przykład jak może rozpoznować, czy dany graf jest spójny.
Definicja 4.40 Graf skierowany (zorientowany) to dowolna para G = (V, E), ze skoń-
czonym zbiorem wierzchoÅ‚ków V i zbiorem krawÄ™dzi E †" V × V .
Rysunek 4.2: Graf skierowany
1 2 3
4 5
W grafie skierowanym krawędz e = (u, v) jest skierowana od wierzchołka u do wierz-
chołka v. Wierzchołek u nazywamy początkiem krawędzi, a wierzchołek v końcem. Na
4.6. Problemy grafowe 107
rysunkach krawędzie skierowane będziemy przedstawiać jako strzałki. Zcieżka (lub dro-
ga) w grafie skierowanym jest to ciąg wierzchołków v0, v1, . . . , vk, taki że dla każdego
i, 1 d" i d" k, wierzchołki vi-1, vi są połączone krawędzią, czyli (vi-1, vi) " E. Wierz-
chołki grafu o n wierzchołach będziemy zwykle oznaczać przez liczby od 1 do n. Jest
kilka sposobów reprezentowania grafu.
Jeżeli maszyna Turinga ma rozpoznawać problemy grafowe, to graf musi być w pewien
sposób zakodowany na jej taśmie wejściowej.
4.6.1 Listy sÄ…siedztwa
Najczęściej używanym sposobem kodowania grafów używanym w tej książce są tak zwa-
ne listy sÄ…siedztwa. Lista sÄ…siedztwa jest postaci
L1; L2; . . . ; Ln
i zawiera zestawione po kolei i poodzielane średnikami listy Lk. Lista Lk jest postaci
k : ik, . . . , ik
1 jk
zaczyna się od k z dwukropkiem, a za nim stoi lista wierzchołków połączonych krawę-
dziami z k. Na przykład lista sąsiedztwa grafu z rysunku 4.2 jest postaci:
1 : 2, 4; 2 : 3, 5; 3 :; 4 : 1; 5 : 4
4.6.2 Macierz sÄ…siedztwa
Inny sposób reprezentacji grafu skierowanego to macierz sąsiedztwa. Dla grafu z n wierz-
choÅ‚kami macierz sÄ…siedztwa A jest wymiaru n × n. Wyraz
1 jeżeli (i, j) " E
ai,j =
0 jeżeli (i, j) " E.
/
Na przykład macierz sąsiedztwa dla grafu z rysunku 4.2 ma następującą postyać:
ëø öø
0 1 0 1 0
ìø ÷ø
0 0 1 0 1
ìø ÷ø
ìø ÷ø
0 0 0 0 0
ìø ÷ø
íø øø
1 0 0 0 0
0 0 0 1 0
108 Rozdział 4. Maszyny Turinga
Rysunek 4.3: Przykład grafu
1 2
3 4
Definicja 4.41 Graf (nieskierowany) G = (V, E) jest to para składająca się ze skończo-
nego zbioru wierzchołków V oraz ze zbioru krawędzi E, gdzie krawędzie to pary wierz-
choÅ‚ków E †" {{u, v} | u, v " V, u = v}.
Graf nieskierowane będziemy traktowali jako skierowane, w których dla każdej nieskiero-
wanej krawędzi {u, v} mamu dwie skierowane krawędzie (u, v) oraz (v, u). Na przykład
lista sÄ…siedztwa grafu z rysunku 2 jest postaci:
1 : 2, 3, 4; 2 : 1, 3; 3 : 1, 2; 4 : 1
A macierz sąsiedztwa następująca:
ëø öø
0 1 1 1
ìø ÷ø
1 0 1 0
ìø ÷ø
íø øø
1 1 0 0
1 0 0 0
4.6.3 Osiągalność w grafie
Jesteśmy teraz gotowi do dokładnego omówienia problemu osiągalności w grafie skiero-
wanym. problem przedstawiamy w następujący sposób.
Problem osiągalności
Wejście: lista sąsiedztwa grafu skierowanego G = (V, E) oraz dwa wierzchołki u i v
Pytanie: czy w G istnieje ścieżka od u do v.
Instancjami problemu są listy sąsiedztwa grafów skierowanych wraz z parami wierz-
chołków. Maszyna Turinga, która rozpoznaje ten problem powinna akceptować te instan-
cje, które kodują grafy z odpowiednią ścieżką. Najpierw przedstawimy deterministycz-
ną maszynę Turinga M1 rozwiązującą ten problem. Maszyna M1 posiada trzy taśmy. Na
pierwszej znajduje się graf G oraz wierzchołki u i v. Na drugiej wypisuje wierzchołki osią-
galne z wierzchołka u. Zaczyna od wypisania u. Następnie pracuje w cyklach. W każdym
kolejnym cyklu:
4.6. Problemy grafowe 109
" zanacza kolejny (niezaznaczony jeszcze) wierzchołek w na drugiej taśmie,
" wypisuje na trzeciej taśmie wszytkie wierzchołki połączone krawędzią z w,
" dla każdego wierzchołka z trzeciej taśmy sprawdza, czy jest on na drugiej taśmie;
jeżeli go nie ma, to jest dopisywany na końcu,
" czyści trzecią taśmę.
Maszyna kończy pracę, albo jeżeli wierzchołek v znajdzie się na trzeciej taśmie (wte-
dy akceptuje), albo gdy zaznaczy wszystkie wierzchołki na drugiej taśmie i nie znajdzie
v (wtedy kończy obliczenie w stanie odrzucającym). Teraz przedstawimy niedetermini-
styczną maszynę M2, która akceptuje ten sam język. Maszyna M2 odgaduje wierzchołek
po wierzchołku ścieżkę prowadzącą od u do v. Posiada dwie taśmy, na pierwszej znajduje
się lista sąsiedztwa grafu G. Na początku wpisuje na drugą taśmę numer wierzchołka u.
Następnie wyszukuje na pierwszej taśmie listę wierzchołków połączonych krawędzią z u.
Wybiera niedeterministycznie jeden z nich i wpisuje jego numer na miejsce numeru wierz-
chołka u. Podobnie odgaduje kolejne wierzchołki ścieżki, aż do odnalezienia wierzchołka
v. Gdy go odnajdzie akceptuje.
Jeżeli w grafie G istnieje ścieżka od u do v, to istnieje obliczenie (ciąg odgadnięć)
prowadzące do konfiguracji akceptującej. Ale i na odwrót, jeżeli istnieje obliczenie akcep-
tujące maszyny, to znaczy, że maszyna odgadła ścieżkę od u do v. Więc maszyna akceptuje
instancje problemu osiągalności.
Zadanie 4.42 Zaprojektuj deterministycznÄ… lub niedeterministycznÄ… maszynÄ™ rozpoznajÄ…-
cą, czy graf skierowany jest silnie spójny. Graf jest silnie spójny, jeżeli dla każdych dwóch
wierzchołków u, v istnieje ścieżka od u do v. [ Pobierz całość w formacie PDF ] - zanotowane.pl
- doc.pisz.pl
- pdf.pisz.pl
- zambezia2013.opx.pl