Języki, automaty i obliczenia/Wykład 12: Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga

{Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga}

Wprowadzenie

W tym wykładzie omówimy języki i gramatyki kontekstowe oraz ich własności. Wprowadzimy

automat liniowo ograniczony i uzasadnimy równość rodziny języków kontekstowych i rodziny języków rozpoznawanych przez automaty liniowo ograniczone. Zdefiniujemy maszynę Turinga i pokażemy równoważność tego modelu z wybranymi innymi modelami obliczeń.

Słowa kluczowe

gramatyka: kontekstowa, rozszerzająca, z markerem końca,

liniowo ograniczona, automat liniowo ograniczony, maszyna Turinga, maszyna wielotaśmowa, maszyna niedeterministyczna.

W tym wykładzie omówimy kolejną rodzinę języków hierarchii Chomsky'ego, a mianowicie języki kontekstowe. Przedstawimy kilka własnosci gramatyk kontekstowych, czyli typu (1) oraz wprowadzimy pojęcie automatu liniowo ograniczonego. Wprowadzimy też najogólniejszy model obliczeń, a mianowicie maszynę Turinga.

Języki kontekstowe

Języki kontekstowe to kolejna rodzina języków w hierarchii Chomsky'ego. Rozszerza ona istotnie rodzinę języków bezkontekstowych. Wykorzystanie tej rodziny języków formalnych jest dość ograniczone. Brak jest bowiem praktycznych metod konstrukcji parserów dla tych gramatyk.

Ta część wykładu prezentuje gramatyki równoważne gramatykom kontekstowym, posiadające pewne określone własności. Te własności wykorzystuje się przy uzasadnieniu faktu, że rodzina języków kontekstowych pokrywa się z rodziną języków rozpoznawanych przez automaty liniowo ograniczone. Biorąc pod uwagę to, że zastosowania tej rodziny języków formalnych nie są powszechne oraz to, że dowody dla przedstawionych poniżej twierdzeń są mocno techniczne postanowiliśmy zrezygnować z rygorystycznej prezentacji tego materiału i pominąć dowody. Zainteresowany Student może je znaleźć w literaturze wskazanej do tego przedmiotu.

Definicja

Gramatykę $G=(V_N,V_T,v_0,P)$ nazywamy rozszerzającą, jeśli każde prawo jest postaci $x\to y$ , gdzie $x,y\in (V_N\cup V_T{)}^{*}$ i spełniona jest nierówność $\mid x\mid \le \mid y\mid$ lub jest to prawo $v_0\to 1$ i wtedy $v_0$ nie występuje po prawej stronie w żadnej produkcji z $P$ .

Wprost z definicji wynika, że gramatyka kontekstowa jest gramatyką rozszerzającą. Prawdziwe jest również następujące twierdzenie.

Twierdzenie

Dla dowolnej gramatyki $G=(V_N,V_T,v_0,P)$ rozszerzającej istnieje równoważna gramatyka kontekstowa.

Wprowadzimy teraz gramatyki z markerem końca.

Definicja

Gramatyką z markerem końca $\mathrm{♯}$ nazywamy gramatykę $G_{\mathrm{♯}}=(V_N\cup \{\mathrm{♯}\},V_T,v_0,P)$ taką, że $\mathrm{♯}\notin V_N\cup V_T$ oraz prawa są postaci: $u\to v$ , $\mathrm{♯}u\to \mathrm{♯}v$ lub $u\mathrm{♯}\to v\mathrm{♯}$ , gdzie $u,v\in (V_N\cup V_T{)}^{*}$ i w słowie $u$ występuje co najmniej jeden symbol nieterminalny z $V_N$ . Językiem generowanym przez tę gramatykę nazywamy zbiór

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L(G_{\sharp })=\{w\in V_{T}^{*}:\: \sharp v_{0}\sharp \mapsto^{*}\sharp w\sharp \}. }

Gramatyka z markerem końca $G_{\mathrm{♯}}$ jest kontekstowa (typu $1$ ), jeśli jej prawa po wymazaniu markera $\mathrm{♯}$ spełniają warunki gramatyki rozszerzającej. Oczywiście dla dowolnej gramatyki kontekstowej istnieje równoważna gramatyka kontekstowa z markerem końca. Prawdziwe jest również następujące twierdzenie:

Twierdzenie

Dla dowolnej gramatyki kontekstowej z markerem końca istnieje równoważna gramatyka kontekstowa.

Dowód

Niech $G_{\mathrm{♯}}=(V_N\cup \{\mathrm{♯}\},V_T,v_0,P)$ będzie dowolną gramatyką kontekstową z markerem końca. Zakładamy, bez ograniczania ogólności rozważań, że w zbiorze $P$ nie występuje prawo $v_0\to 1$ (po wymazaniu markera $\mathrm{♯}$ ). Dla każdego symbolu $x$ ze zbioru $V=V_N\cup V_T$ określamy trzy symbole Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \, ^{\sharp }x,x^{\sharp },^{\: \sharp }x^{\sharp } } oraz oznaczamy odpowiednio przez ${}^{\mathrm{♯}}V,V^{\mathrm{♯}}{,}^{\mathrm{♯}}{V}^{\mathrm{♯}}$ zbiory tych symboli. Dla $u=u_1...u_k$ takiego, że $k\ge 1$ i $u_i\in V$ dla $i=1,...,k$ wprowadzamy także następujące oznaczenia:

${}^{\mathrm{♯}}u={}^{\mathrm{♯}}{u}_1{u}_2...u_k$ , $u^{\mathrm{♯}}=u_1...u_{k-1}{u}_k^{\mathrm{♯}}$ oraz ${}^{\mathrm{♯}}{u}^{\mathrm{♯}}={}^{\mathrm{♯}}{u}_1{u}_2...u_{k-1}{u}_k^{\mathrm{♯}}$ gdy $k>1$ .

Przy takich oznaczeniach definiujemy gramatykę

$G_1=(V_N\cup {}^{\mathrm{♯}}V\cup V^{\mathrm{♯}}{\cup }^{\mathrm{♯}}{V}^{\mathrm{♯}},V_T,{}^{\mathrm{♯}}{v}_0^{\mathrm{♯}},P_1),$

w której zbiór praw $P_1$ składa się ze wszystkich praw uzyskanych zgodnie z poniższymi warunkami:

1. jeśli $u\to w\in P$ , to Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle u\rightarrow w,\: ^{\#}u\rightarrow \, ^{\#}w,\: u^{\#}\rightarrow w^{\#},\: ^{\#}u^{\#}\rightarrow \, ^{\#}w^{\#}\in P_{1} }
2. jeśli ${}^{\mathrm{\#}}u\to {}^{\mathrm{\#}}w\in P$ , to Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \: u^{\#}\rightarrow w^{\#},\: ^{\#}u^{\#}\rightarrow \, ^{\#}w^{\#}\in P_{1} }
3. jeśli $u^{\mathrm{\#}}\to w^{\mathrm{\#}}\in P$ , to Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle u^{\#}\rightarrow w^{\#},\: ^{\#}u^{\#}\rightarrow \, ^{\#}w^{\#}\in P_{1} }
4. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \, ^{\#}x\rightarrow x,\: x^{\#}\rightarrow x,\: ^{\#}x^{\#}\rightarrow x\in P_{1} }

dla wszystkich $x\in V$ .

Określona w ten sposób gramatyka $G_1$ jest gramatyką rozszerzającą i równoważną wyjściowej. Dla gramatyki $G_1$ istnieje, zgodnie z poprzednim twierdzeniem, równoważna gramatyka kontekstowa, co kończy dowód twierdzenia.

$\mathrm{♢}$

Prawdziwe jest także następujące twierdzenie (porównaj Uzupelnic thr_1|)

Twierdzenie

Dla dowolnej gramatyki kontekstowej (rozszerzającej) istnieje równoważna gramatyka kontekstowa (rozszerzająca) o tej własności, że każde prawo, w którym występuje symbol terminalny, jest postaci $v\to a$ , gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle v\in V_{N},\: a\in V_{T} } .

Mówimy, że gramatyka $G$ jest rzędu $n>0$ , jeśli dla każdego prawa $x\to y$ tej gramatyki spełniony jest warunek $\mid x\mid \le n$ i $\mid y\mid \le n$ . Kolejne twierdzenie stwierdza możliwość dalszego uproszczenia praw gramatyki rozszerzającej.

Twierdzenie

Dla każdej gramatyki rozszerzającej istnieje równoważna gramatyka rozszerzająca rzędu $2$ .

Na koniec wprowadzimy jeszcze jeden rodzaj gramatyk równoważnych gramatykom kontekstowym. Są to mianowicie gramatyki liniowo ograniczone.

Definicja

Gramatyka $G=(V_N,V_T,v_0,P)$ jest liniowo ograniczona, jeśli każde prawo jest jednej z następujących postaci:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle v_{0}\rightarrow v_{0}v,\: v_{1}v_{2}\rightarrow z_{1}z_{2},\: v\rightarrow x, }

gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle x\in V_{N}\cup V_{T},\: v,v_{1},v_{2},z_{1},z_{2}\in V_{N} } oraz $v_0\notin \{x,z_1,z_2,v\}$ .

Twierdzenie

Dla dowolnej gramatyki kontekstowej $G$ istnieje gramatyka liniowo ograniczona $G_1$ , która jest równoważna $G$ lub też generuje język $L(G)\setminus \{1\}$ .

Dowód

W świetle poprzednich twierdzeń możemy przyjąć, że gramatyka kontekstowa $G=(V_N,V_T,v_0,P)$ ma prawa wyłącznie w następujących postaciach:

1. $v_0\to 1$
2. $v\to x$ gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle v\in V_{N},\: x\in V_{N}\cup V_{T} }
3. $v\to v_1{v}_2$ gdzie $v,v_1,v_2\in V_N$
4. $v_1{v}_2\to v_3{v}_4$ gdzie $v_1,v_2,v_3,v_4\in V_N$

Określamy gramatykę $G_1=(V_N\cup \{z_0,z_1\},V_T,z_0,P_1)$ , gdzie $z_1,z_2$ są nowymi symbolami nieterminalnymi, a więc nie należą do $V_N$ . Natomiast zbiór praw $P_1$ składa się ze wszystkich praw ze zbioru $P$ postaci 2 i 4 oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle z_{0}\rightarrow z_{0}z_{1},\: z_{0}\rightarrow v_{0},\: } praw Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle z_{1}v\rightarrow vz_{1},\: vz_{1}\rightarrow z_{1}v } dla $v\in V_N$ i praw $v_1{z}_1\to v_3{v}_4$ dla każdego prawa postaci 4 w gramatyce $G$ . Skonstruowana gramatyka jest liniowo ograniczona i spełnia tezę twierdzenia.

$\mathrm{♢}$

Automat liniowo ograniczony

Określimy teraz systemy, zwane automatami liniowo ograniczonymi, który rozpoznają języki kontekstowe.

Definicja

Automatem liniowo ograniczonym nazywamy system ${{𝒜}}_{LO}=({\mathrm{\Sigma }}_T,S,P,s_0,S_F)$ , w którym ${\mathrm{\Sigma }}_T$ jest skończonym alfabetem, $S$ skończonym zbiorem stanów, $S\cap {\mathrm{\Sigma }}_T=\mathrm{\varnothing }$ oraz wyróżniony jest podzbiór ${\mathrm{\Sigma }}_I\subset {\mathrm{\Sigma }}_T$ . Zbiór ${\mathrm{\Sigma }}_T$ zwany jest alfabetem ta{s}my, a ${\mathrm{\Sigma }}_I$ - alfabetem wej{s}ciowym. Wyróżnione są także: element $\mathrm{\#}\in {\mathrm{\Sigma }}_T\setminus {\mathrm{\Sigma }}_I$ zwany markerem końca, stan pocz{a}tkowy $s_0\in S$ oraz $S_F\subset S$ - zbiór stanów ko{n}cowych. Natomiast relacja przejść $P\subset (S\times {\mathrm{\Sigma }}_T)\times (S\times {\mathrm{\Sigma }}_T\times \{-1,0,1\})$ spełnia następujące warunki:

1. jeśli $(s_1,\mathrm{\#})P(s_2,a,k)$ , to $a=\mathrm{\#},$
2. jeśli $(s_1,a)P(s_2,\mathrm{\#},k)$ , to $a=\mathrm{\#}.$

Fakt, że $(s_1,a)P(s_2,b,k)$ , zapisujemy zazwyczaj jako $(s_1,a)\to (s_2,b,k)$ . Do opisu działania automatu liniowo ograniczonego wygodnie jest wprowadzić pojęcie konfiguracji (podobnie jak dla automatów ze stosem).

Konfiguracją automatu liniowo ograniczonego jest słowo $vsw\in ({\mathrm{\Sigma }}_T\cup S{)}^{*}$ , w którym $s\in S,v,w\in {\mathrm{\Sigma }}_T^{*}$ . Pomiędzy dwoma konfiguracjami $d_1,d_2$ zachodzi relacja bezpośredniego następstwa $d_1\mapsto d_2$ wtedy i tylko wtedy, gdy spełniony jest jeden z niżej wypisanych warunków, gdzie $s_1,s_2\in S$ , $a,b,c\in {\mathrm{\Sigma }}_T$ oraz $v,w\in {\mathrm{\Sigma }}_T^{*}$

1. $d_1=v{s}_{1}aw$ , $d_2=v{s}_{2}bw$ oraz $(s_1,a)P(s_2,b,0)$
2. $d_1=v{s}_{1}aw$ , $d_2=vb{s}_{2}w$ oraz $(s_1,a)P(s_2,b,1)$
3. $d_1=vc{s}_{1}aw$ , $d_2=v{s}_{2}cbw$ oraz $(s_1,a)P(s_2,b,-1)$

Przechodnie domknięcie relacji $\mapsto$ oznaczać będziemy symbolem ${\mapsto }^{*}$ i określać mianem obliczenia wykonanego przez automat liniowo ograniczony.

{}

Język rozpoznawany przez automat liniowo ograniczony ${{𝒜}}_{LO}$ to zbiór słów nad alfabetem ${\mathrm{\Sigma }}_I$ , pod działaniem których automat wykonuje obliczenie prowadzące do stanu końcowego, czyli

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L(\mathcal{A}_{LO})=\left\{ w\in \Sigma _{I}^{*}\: :\: s_{0}\#w\#\mapsto^{*}vs,\; v\in \Sigma _{T}^{*},\, s\in S_{F}\right\} .}

Język $L\subset {\mathrm{\Sigma }}_I^{*}$ jest rozpoznawany (akceptowany) przez automat liniowo ograniczony, jeśli istnieje automat ${{𝒜}}_{LO}$ taki, że ${ℒ}({{𝒜}}_{LO})=L.$

{}{2900sp}

(2256,2000)(1100,-1200)

(1000,0){( 1, 0){3400}}

(1100,0)(300,0){3}{(0, 1){300}}

(1200,100){ $\mathrm{♯}$ }

(1900,100){ $\cdots$ }

(2300,0)(300,0){3}{(0, 1){300}}

(2400,100){ $c$ }

(2700,100){ $a$ }

(3100,100){ $\cdots$ }

(3600,0)(300,0){3}{(0, 1){300}}

(4000,100){ $\mathrm{♯}$ }

(1707,0){( 1, 0){2393}}

(1000,300){( 1, 0){3400}}

{(2750,-342){( 0, 1){300}} }

(5450,0){( 1, 0){3400}}

(5600,0)(300,0){3}{(0, 1){300}}

(5700,100){ $\mathrm{♯}$ }

(6400,100){ $\cdots$ }

(6800,0)(300,0){3}{(0, 1){300}}

(6900,100){ $c$ }

(7200,100){ $b$ }

(7600,100){ $\cdots$ }

(8100,0)(300,0){3}{(0, 1){300}}

(8500,100){ $\mathrm{♯}$ }

(5450,300){( 1, 0){3400}}

{(6950,-342){( 0, 1){300}} }

(2257,-1235){(893,893){ Parser nie mógł rozpoznać (nieznana funkcja „\large”): {\displaystyle \displaystyle { \large s_{1}} } }}

(6500,-1235){(893,893){ Parser nie mógł rozpoznać (nieznana funkcja „\large”): {\displaystyle \displaystyle { \large s_{2}} } }}

{0.2cm}

Opiszemy teraz możliwe ruchy automatu liniowo ograniczonego. Automat ten mo{z}e czyta{c} s{}owo wej{s}ciowe w dwóch kierunkach. Jego głowica mo{z}e porusza{c} si{e} w lewo lub w prawo. Automat mo{z}e wymienia{c} czytan{a} liter{e} na inn{a}, ale nie rozszerza miejsca zaj{e}tego na ta{s}mie przez czytane słowo. Działa niedeterministycznie. Czytaj{a}c liter{e} $a$ będąc w stanie $s$ automat ma kilka mo{z}liwo{s}ci dzia{}ania. Może mianowicie:

1. zamieni{c} literę na inn{a} liter{e} i/lub zmienić stan na inny - zgodnie

z warunkiem 1. Głowica czytająca automatu pozostaje w poprzedniej pozycji,

1. zamieni{c} literę na inn{a} liter{e} i/lub zmienić stan na inny - zgodnie

z warunkiem 2. Głowica czytająca automatu przesuwa się w prawo,

1. zamieni{c} literę na inn{a} liter{e} i/lub zmienić stan na inny - zgodnie

z warunkiem 3. Głowica czytająca automatu przesuwa się w lewo.

Związek pomiędzy rodziną języków kontekstowych a wprowadzoną rodziną automatów liniowo ograniczonych ustalają ponizsze twierdzenia.

Twierdzenie

Dla dowolnego języka kontekstowego $L$ istnieje automat liniowo ograniczony ${{𝒜}}_{LO}$ taki, że ${ℒ}({{𝒜}}_{LO})=L$ .

Dowód

Można założyć, bez ograniczenia ogólności naszych rozważań, że gramatyka $G=(V_N,V_T,v_0,P)$ generująca język $L$ ma prawa wyłącznie następujących postaci:

1. (G) $v\to x$ , gdzie $v\in V_N,x\in V_N\cup V_T,x\ne v_0$
2. (G) $v_0\to v_0{v}_1$ , gdzie $v_1\in V_N,v_1\ne v_0$
3. (G) $v_1{v}_2\to v_3{v}_4$ , gdzie $v_1,...,v_4\in V_N,v_3,v_4\ne v_0$
4. (G) $v_0\to 1,$ jeśli $1\in L$ .

Określamy automat liniowo ograniczony ${{𝒜}}_{LO}=({\mathrm{\Sigma }}_T,S,P,s_0,S_F)$ , przyjmując ${\mathrm{\Sigma }}_T=V_N\cup V_T\cup \{\mathrm{\#},\mathrm{♭}\}$ , $S=\{s_0,s_1,s_2,s_3,s_4\}\cup \{s_{v_1}:v_1{v}_2\to v_3{v}_4\in P\}$ , ${\mathrm{\Sigma }}_I=V_N\cup V_T$ , $S_F=\{s_3\}$ , $s_0$ - stan początkowy. Relacja przejść automatu ${{𝒜}}_{LO}$ zdefiniowana jest poniżej:

1. (A) $(s_0,\mathrm{\#})\to (s_0,\mathrm{\#},1)$
2. (A) $(s_0,\mathrm{\#})\to (s_4,\mathrm{\#},1)$ jeśli $1\in L$
3. (A) $(s_0,x)\to (s_0,x,1)$ , $(s_0,x)\to (s_0,x,-1)$

dla każdego $x\in V_N\cup V_T$

1. (A) $(s_0,x)\to (s_0,v,0)$ jeśli $v\to x\in P$

i $x\ne v_0$

1. (A) $(s_0,v_3)\to (s_{v_1},v_1,1),(s_{v_1},v_4)\to (s_0,v_2,0)$

jeśli $v_1{v}_2\to v_3{v}_4\in P$

1. (A) $(s_0,v_0)\to (s_1,v_0,-1)$
2. (A) $(s_1,\mathrm{\#})\to (s_2,\mathrm{\#},1)$
3. (A) $(s_1,\mathrm{♭})\to (s_2,\mathrm{♭},1)$
4. (A) $(s_2,v_0)\to (s_3,\mathrm{♭},1)$
5. (A) $(s_3,v_1)\to (s_0,v_0,0)$ , gdy $v_0\to v_0{v}_1\in P$
6. (A) $(s_3,\mathrm{\#})\to s_3,\mathrm{\#},1),(s_4,\mathrm{\#})\to (s_3,\mathrm{\#},1)$

Określony automat ${{𝒜}}_{LO}$ rozpoznaje tylko te słowa, które są generowane przez gramatykę $G$ , symulując wstecz każde wyprowadzenie gramatyki $G$ .

$\mathrm{♢}$

Prawdziwe jest również następujące twierdzenie.

Twierdzenie

Dla dowolnego języka $L$ rozpoznawanego przez automat liniowo ograniczony ${{𝒜}}_{LO}$ istnieje gramatyka kontekstowa $G$ taka, że $L(G)=L$ .

W dowodzie konstruuje się odpowiednią gramatykę.Zasada tej konstrukcji jest następująca. Z symbolu startowego gramatyka generuje dowolne słowa, ustawiając zawsze na prawym końcu symbol nieterminalny związany z przejściem automatu do stanu końcowego. Następnie korzysta się z możliwości zamiany takiego symbolu nieterminalnego na inne. W ten sposób gramatyka symuluje wstecz działanie automatu, wprowadzając symbole nieterminalne odpowiadające stanom automatu. Dojście do stanu początkowego automatu w tej symulacji jest równoznaczne z usunięciem ostatniego symbolu nieterminalnego i wygenerowaniem słowa dokładnie tego samego, które rozpoznaje automat.

Udowownimy teraz zamkniętość rodziny języków kontekstowych ze względu na iloczyn mnogościowy.

Twierdzenie

Dla dowolnych języków kontekstowych $L_1,L_2\subset A^{*}$ iloczyn mnogościowy tych języków $L_1\cap L_2$ jest językiem kontekstowym

Dowód

( szkic) Załóżmy, że języki $L_1,L_2$ są rozpoznawane przez automaty liniowo ograniczone, ${{𝒜}}_{LO}^1$ i ${{𝒜}}_{LO}^2$ . Opiszemy konstrukcję automatu liniowo ograniczonego ${{𝒜}}_{LO}$ , który rozpoznawać będzie wyłącznie słowa akceptowane równocześnie przez oba automaty. Działanie tego automatu jest następujące. Każde słowo będzie czytane trzy razy. Przy pierwszym czytaniu automat ${{𝒜}}_{LO}$ dubluje litery, to znaczy w miejsce litery $a$ wprowadza parę $(a,a)$ . Po zakończeniu tej procedury automat wraca do skrajnej lewej pozycji i rozpoczyna symulację automatu ${{𝒜}}_{LO}^1$ . Jeśli ta symulacja doprowadzi do zaakceptowania czytanego słowa przez automat ${{𝒜}}_{LO}^1$ , to automat ${{𝒜}}_{LO}$ rozpoczyna obliczenie od początku, symulując teraz pracę automatu ${{𝒜}}_{LO}^2$ . Jeśli i ta symulacja zakończy się zaakceptowaniem czytanego słowa, to automat przechodzi do ustalonego stanu końcowego, a to oznacza akceptację tego słowa. Działając w opisany sposób automat ${{𝒜}}_{LO}$ rozpoznaje język $L_1\cap L_2$ , a to w świetle udowodnionego powyżej twierdzenia oznacza, że przecięcie języków kontekstowych $L_1\cap L_2$ jest językiem kontekstowym.

$\mathrm{♢}$

Ponieważ dalsze własności domknietości rodziny języków kontekstowych pokrywają się z własnościami języków typu (0), więc omówimy te własności wspólnie, co bedzie mieć miejsce w następnym wykładzie.

Maszyna Turinga

Przejdziemy teraz do prezentacji ogólnego modelu maszyny liczącej, który został wprowadzony w 1936 roku przez Alana M. Turinga. Na cześć swego autora został on nazwany (jednotaśmową) maszyną Turinga. Model ten jest podobny w swojej idei do rozważanych wcześniej automatów liniowo ograniczonych, przy czym jednym z podstawowych założeń ( i różnic względem automatów) jest nieskończony dostęp do pamięci. Maszyna Turinga może wydawać się na początku pojęciem bardzo abstrakcyjnym. Jednak, jak później zobaczymy, stanowi ona jedną z podstawowych koncepcji współczesnej informatyki. Pozwala na formalne zdefiniowanie pojęcia algorytmu oraz jego złożoności obliczeniowej. Jako model obliczeń pozwala odpowiedzieć także na bardzo ważne pytanie: Czy każdy problem można rozwiązać algorytmicznie ?

Jednotaśmowa maszyna Turinga jest podobna w swej idei do automatu liniowo ograniczonego, pominięte jednak zostaje, jak wspomnieliśmy, ograniczenie dostępu do pamięci. Omawiana maszyna jest abstrakcyjnym tworem w skład którego wchodzą:

--

dwustronnie nieskończona taśma zbudowana z komórek

zawierających symbole z pewnego zadanego alfabetu

--

głowica która może czytać i zapisywać symbole w

komórkach taśmy oraz poruszać się w prawo lub lewo o jedną komórkę lub pozostawać na tej samej pozycji podczas jednego kroku czasowego

--

działający sekwencyjnie mechanizm odpowiedzialny za sterowanie maszyną.

Mechanizm ten na podstawie symbolu odczytanego z komórki pod głowicą oraz stanu w którym aktualnie znajduje się maszyna, dokonuje zapisu symbolu w tejże komórce, przechodzi do kolejnego stanu i przesuwa głowicę w prawo, lewo lub też nie zmienia pozycji głowicy.

Podamy teraz formalną definicję maszyny Turinga. Aby zachować analogię do poprzednich wykładów, zdefiniujemy maszynę w języku konfiguracji.

Definicja

(Jednotaśmowa deterministyczna) maszyna Turinga jest to system $\mathbf{𝐌}\mathbf{𝐓}=({\mathrm{\Sigma }}_T,S,f,s_0,S_F)$ , w którym ${\mathrm{\Sigma }}_T$ jest skończonym alfabetem, $S$ skończonym zbiorem stanów, $S\cap {\mathrm{\Sigma }}_T=\mathrm{\varnothing }$ oraz wyróżniony jest podzbiór ${\mathrm{\Sigma }}_I\subset {\mathrm{\Sigma }}_T$ . Zbiór ${\mathrm{\Sigma }}_T$ zwany jest alfabetem taśmy, a ${\mathrm{\Sigma }}_I$ - alfabetem wejściowym. Wyróżnione są także: element $\mathrm{\#}\in {\mathrm{\Sigma }}_T\setminus {\mathrm{\Sigma }}_I$ zwany markerem końca, stan początkowy $s_0\in S$ oraz $S_F\subset S$ - zbiór stanów końcowych. Natomiast funkcja przejść jest funkcją częściową Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle f:\: (S\times \Sigma _{T})\rightarrow (S\times \Sigma _{T}\times \{-1,0,1\} } .

Konfiguracją maszyny Turinga jest słowo $vsw\in ({\mathrm{\Sigma }}_T\cup S{)}^{*}$ , w którym $s\in S,v,w\in {\mathrm{\Sigma }}_T^{*}$ . Pomiędzy dwiema konfiguracjami $d_1,d_2$ zachodzi relacja bezpośredniego następstwa $d_1\mapsto d_2$ wtedy i tylko wtedy, gdy spełniony jest jeden z niżej wypisanych warunków, gdzie $s_1,s_2\in S$ , $a,b,c\in {\mathrm{\Sigma }}_T$ oraz $v,w\in {\mathrm{\Sigma }}_T^{*}$

1. $d_1=v{s}_{1}aw$ , $d_2=v{s}_{2}bw$ oraz $f(s_1,a)=(s_2,b,0)$
2. $d_1=v{s}_{1}aw$ , $d_2=vb{s}_{2}w$ oraz $f(s_1,a)=(s_2,b,1)$

i $w\ne 1$

1. $d_1=v{s}_1\mathrm{\#}$ , $d_2=vb{s}_2\mathrm{\#}$ oraz $f(s_1,\mathrm{\#})=(s_2,b,1)$
2. $d_1=vc{s}_{1}aw$ , $d_2=v{s}_{2}cbw$ oraz $f(s_1,a)=(s_2,b,-1)$
3. $d_1=s_1\mathrm{\#}w$ , $d_2=s_2\mathrm{\#}bw$ oraz $f(s_1,\mathrm{\#})=(s_2,b,-1)$

Przechodnie domknięcie relacji $\mapsto$ oznaczać będziemy symbolem ${\mapsto }^{*}$ i określać mianem obliczenia wykonanego przez maszynę Turinga. Konfiguracja $d_1\in ({\mathrm{\Sigma }}_T\cup S{)}^{*}$ jest końcowa, jeśli stąd, że $d_1\mapsto d_2$ , wynika $d_2=d_1.$ Mówimy, że maszyna Turinga zatrzymuje się w $d_1$ wtedy i tylko wtedy, gdy $d_1$ jest konfiguracją końcową.

Zauważmy, że wprowadzenie markera końca jest zabiegiem czysto formalnym. Pozwala on z jednej strony na oznaczenie słowa wejściowego a z drugiej strony wskazuje na elementy taśmy które były zmieniane (czy to przez wprowadzenie słowa wejściowego czy też poprzez ruch głowicy).

Definicja

Język rozpoznawany przez maszynę Turinga $MT$ jest to zbiór

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L(\mathbf{MT})=\left\{ w\in \Sigma _{T}^{*}\: :\: \sharp s_{0}w\sharp \mapsto^{*}\sharp w_{1}s_{F}w_{2}\sharp ,\; dla\: pewnych\: w_{1},w_{2}\in \Sigma _{T}^{*},s_{F}\in S_{F}\right\} .}

Język $L\subset {\mathrm{\Sigma }}_I^{*}$ jest rozpoznawany (akceptowany) przez maszynę Turinga, jeśli istnieje $MT$ taka, że $L({ℳ}{𝒯})=L.$ Klasę języków rozpoznawanych przez maszynę Turinga oznaczamy ${ℒ}(MT)$ .

We wprowadzonym przez nas ujęciu formalnym, działanie maszyny Turinga należy wyobrażać sobie następująco. W pierwszym etapie na taśmę zostają zapisane symbole słowa wejściowego (z alfabetu ${\mathrm{\Sigma }}_I$) a następnie komórki przyległe zostają oznaczone symbolami $\mathrm{♯}$. Jednocześnie maszyna jest sprowadzana do stanu $s_0$ a głowica zostaje ustawiona nad pierwszym symbolem słowa wejściowego. W tym momencie rozpoczyna się sekwencyjne przetwarzanie zawartości taśmy przez maszynę. Jeśli maszyna "zatrzyma się", tzn. w dwóch kolejnych chwilach czasowych nie wykona ruchu i jednocześnie nie zmieni stanu i symbolu taśmy, sprawdzany jest jej aktualny stan. Jeśli stan był akceptujący (czyli należał do zbioru $S_F$) to maszyna zaakceptowała słowo, w przeciwnym razie słowo odrzuciła (gdyż nie może już osiągnąć stanu ze zbioru $S_F$). Należy zwrócić uwagę na to, że dla niektórych konfiguracji początkowych maszyna może nigdy się nie zatrzymać, a mimo to słowo zostanie przez nią zaakceptowane. To samo tyczy się odrzucania słów, jednak w tej sytuacji dowód, że słowo nie zostanie zaakceptowane może być problematyczny. Zaprezentowane podejście ma na celu uproszczenie i tak już dość technicznych dowodów twierdzeń pojawiających się w tym wykładzie. Związki pomiędzy akceptowaniem a zatrzymywaniem maszyny Turinga zostaną skomentowane później (zob. Wniosek Uzupelnic WnL+Stop|). W pierwszej kolejności przedstawiamy dwa przykłady:

Przykład

Skonstruujemy maszynę Turinga $M{T}_1$ która rozpoznaje język postaci $L=\{0^{2^n}:n\ge 0\}$. Zamierzone działanie maszyny $M{T}_1$ można opisać następująco:

1.

Przejdź od lewego markera do prawego zaznaczając symbolem $\mathrm{♢}$ co

drugie $0$.

2.

Jeśli było tylko jedno $0$ to akceptuj.

3.

Jeśli w kroku 1. obszar pomiędzy markerami zawierał

nieparzystą ilość $0$ to odrzuć.

4.

Powróć do lewego markera.

5.

Powtórz działanie od 1.

Zwróćmy uwagę, że o ile jasne jest w jaki sposób maszyna ma akceptować słowa wejściowe, odrzucanie tych słów nie zostało zdefiniowane. Aby ominąć ten problem, wprowadzimy jeden dodatkowy stan (nie należący do stanów końcowych) po osiągnięciu którego maszyna się zatrzymuje (tzn. nie wykonuje ruchów i przepisuje na taśmie wciąż ten sam symbol).

Określamy kolejno elementy składowe maszyny $M{T}_1$:

${\mathrm{\Sigma }}_I=\left\{0\right\},{\mathrm{\Sigma }}_T=\{0,\mathrm{♢},\mathrm{♣},\mathrm{♯}\}$ $S=\{s_0,s_1,s_2,s_3,s_4,s_A,s_R\},S_F=\left\{s_A\right\}$

Pozostaje jeszcze zdefiniować funkcję przejść.

{

Przykład

Przedstawimy maszynę Turinga $M{T}_2$ akceptującą język

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L=\left\{w \overleftarrow{w} \: : \: w\in \left\{0,1\right\}^*\right\} }

gdzie $\overleftarrow{w}$ oznacza lustrzane odbicie słowa $w$. Elementy języka $L$ nazywamy palindromami. Definiujemy alfabet maszyny

${\mathrm{\Sigma }}_I=\{0,1\},{\mathrm{\Sigma }}_T=\{0,1,\mathrm{♯}\}$

oraz zbiory stanów

$S=\{s_0,r_0,{r_0}^{\prime },q_0,r_1,{r_1}^{\prime },q_1,l,s_A,s_R\},S_F=\left\{s_A\right\}$

Funkcję przejść maszyny $M{T}_2$ określa tabela:

{

Inne możliwe definicje maszyn Turinga

Istnieje kilka możliwych definicji maszyny Turinga, które jak się okazuje są równoważne pod względem możliwości obliczeniowych (tzn. rozpoznają dokładnie tą samą klasę języków). Naszkicujemy kilka wybranych podejść.

Maszyna wielotaśmowa

W tym modelu zakłada się że głowica ma do dyspozycji nie tylko jedną ale wiele taśma na których może zapisywać i odczytywać symbole. Zakłada się przy tym że słowo wejściowe znajduje się na pierwszej taśmie. Aby symulować maszynę wielotaśmową na jednej taśmie należy zamienić alfabet taśmy na alfabet $({\mathrm{\Sigma }}_T{)}^k$ gdzie $k$ oznacza ilość taśm. W tym momencie zapis na taśmie $i$-tej jest realizowany przez zmianę odpowiedniej współrzędnej litery z nowego alfabetu (zob. Rys. 4.a). Czyli w opisywanym przypadku funkcja przejść będzie operowała na następujących zbiorach:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle f:\: (S\times \Sigma^k_{T} )\rightarrow (S \times \Sigma^k_{T} \times \{-1,0,1\} ). }

Taśma jednostronnie nieskończona

Model ten zakłada że taśma jest ograniczona z jednej ze stron. Różnica w porównaniu z rozważaną przez nas maszyną Turinga polega na tym że nie jest dozwolone przesuwanie lewego markera (tzn. funkcja przejść nie może zawierać przejść typu (Uzupelnic trans5|)). W tej sytuacji aby symulować maszynę z taśmą obustronnie nieskończoną na maszynie z taśmą ograniczoną z jednej strony wystarczy zasymulować taśmę obustronnie nieskończoną poprzez rozszerzenie alfabetu (zob. Rys. 4.b).

RYSUNEK ja-lekcja12-w-rys4

Wielogłowicowa maszyna wielotaśmowa

W tym podejściu zakłada się dodatkowo, że każda z taśm posiada swoją głowicę. Inaczej mówiąc mamy do czynienia z iloczynem kartezjańskim $k$ niezależnych maszyn jednotaśmowych. Akceptowany język jest w tym momencie $k$-wymiarowy. Oczywiście, słowo postaci $(w,1,\dots ,1)\in ({\mathrm{\Sigma }}_T^{*}{)}^k$ można w naturalny sposób utożsamiać z $w\in {\mathrm{\Sigma }}_T$. Z drugiej strony maszynę wielogłowicową można symulować na jednotaśmowej w następujący sposób:

1. Jako zbiór stanów bierzemy $S^k$.
2. Słowa startowe $w_1,\dots ,w_k$ zapisujemy jako konfigurację

początkową maszyny jednotaśmowej w postaci:

$\mathrm{♯}(s_0{)}^k\mathrm{\$}\dot{1}{w}_1\mathrm{\$}\dot{2}{w}_2\mathrm{\$}\dots \mathrm{\$}\dot{k}{w}_k\mathrm{\$}$

Symbole $\mathrm{\$}$ mają za zadanie wirtualnego rozdzielenia taśm. Symbole $\dot{i}$ wskazują na położenie $i$-tej głowicy na taśmie.

1. W trakcie symulacji przechodzimy pomiędzy markerami i

wykonujemy przejścia dla kolejnych głowic.

Widać już, że formalne podanie funkcji przejść jest w omawianym przypadku bardzo techniczne. Musimy zapewnić możliwość poszerzania obszaru zapisu na poszczególnych taśmach, co jest realizowane poprzez dopisanie nowego symbolu i przepisywanie przyległych symboli aż do markera włącznie. Następnie należy wrócić do poprzedniego miejsca zapisu i symulować działanie kolejnych głowic. Wymaga to wprowadzenia sporej liczby stanów pomocniczych. Nie będziemy wchodzić w te techniczne szczegóły. Mamy nadzieję że sama idea konstrukcji jest w tym momencie jasna.

Najbardziej ogólna definicja maszyny tego typu dopuszcza dodatkowo aby głowice mogły przeglądać pozostałe taśmy, dzięki czemu zapewnia się komunikację między głowicami. Symulacja takiej maszyny na jednej taśmie jest podobna w swej idei do metody przedstawionej wcześniej.

Maszyna niedeterministyczna

Ten typ maszyn ma ogromne znaczenie dla teorii złożoności. Z tego powodu przyglądniemy mu się dokładniej. Różnica pomiędzy niedeterministyczną maszyną Turinga a maszyną deterministyczną polega na tym że funkcja przejść może pozwalać na kilka różnych przejść na skutek tego samego symbolu czytanego (gdyż funkcja przejść w tym przypadku będzie multi-funkcją).

Definicja

(Jednotaśmowa) niedeterministyczna maszyna Turinga jest to system $\mathbf{𝐍}\mathbf{𝐌}\mathbf{𝐓}=({\mathrm{\Sigma }}_T,S,f,s_0,S_F)$ w którym ${\mathrm{\Sigma }}_T$ jest skończonym alfabetem, $S$ skończonym zbiorem stanów, $S\cap {\mathrm{\Sigma }}_T=\mathrm{\varnothing }$ oraz wyróżniony jest podzbiór ${\mathrm{\Sigma }}_I\subset {\mathrm{\Sigma }}_T$ . Podobnie jak poprzednio zbiór ${\mathrm{\Sigma }}_T$ zwany jest alfabetem taśmy, a ${\mathrm{\Sigma }}_I$ - alfabetem wejściowym. Wyróżnione są także: element $\mathrm{\#}\in {\mathrm{\Sigma }}_T\setminus {\mathrm{\Sigma }}_I$ zwany markerem końca, stan początkowy $s_0\in S$ oraz $S_F\subset S$ - zbiór stanów końcowych. Natomiast funkcja przejść jest funkcją częściową Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle f:\: (S\times \Sigma _{T})\rightarrow \mathcal{P}(S\times \Sigma _{T}\times \{-1,0,1\}) } gdzie ${𝒫}(A)$ oznacza zbiór podzbiorów zbioru $A$.

Konfiguracją maszyny Turinga jest słowo $vsw\in ({\mathrm{\Sigma }}_T\cup S{)}^{*}$ , w którym $s\in S,v,w\in {\mathrm{\Sigma }}_T^{*}$ , przy czym pomiędzy dwiema konfiguracjami $d_1,d_2$ zachodzi relacja bezpośredniego następstwa $d_1\mapsto d_2$ wtedy i tylko wtedy, gdy spełniony jest jeden z niżej wypisanych warunków, gdzie $s_1,s_2\in S$ , $a,b,c\in {\mathrm{\Sigma }}_T$ oraz $v,w\in {\mathrm{\Sigma }}_T^{*}$

1. $d_1=v{s}_{1}aw$ , $d_2=v{s}_{2}bw$ oraz $f(s_1,a)\ni (s_2,b,0)$
2. $d_1=v{s}_{1}aw$ , $d_2=vb{s}_{2}w$ oraz $f(s_1,a)\ni (s_2,b,1)$

i $w\ne 1$

1. $d_1=v{s}_1\mathrm{\#}$ , $d_2=vb{s}_2\mathrm{\#}$ oraz $f(s_1,\mathrm{\#})\ni (s_2,b,1)$
2. $d_1=vc{s}_{1}aw$ , $d_2=v{s}_{2}cbw$ oraz $f(s_1,a)\ni (s_2,b,-1)$
3. $d_1=s_1\mathrm{\#}w$ , $d_2=s_2\mathrm{\#}bw$ oraz $f(s_1,\mathrm{\#})\ni (s_2,b,-1)$

Tak jak poprzednio, przechodnie domknięcie relacji $\mapsto$ oznaczać będziemy symbolem ${\mapsto }^{*}$ i określać mianem obliczenia wykonanego przez maszynę Turinga. Konfiguracja $d_1\in ({\mathrm{\Sigma }}_T\cup S{)}^{*}$ jest końcowa, jeśli stąd, że $d_1\mapsto d_2$ , wynika $d_2=d_1.$

Pomimo tego, że postawiona definicja maszyny niedeterministycznej jest bardzo podobna do maszyny deterministycznej występuje tutaj jedna bardzo istotna różnica. Słowo wejściowe może prowadzić do wielu różnych obliczeń wykonanych, w szczególności jedno z obliczeń może doprowadzać do zatrzymania maszyny a inne nie.

Przykład maszyny niedeterministycznej podamy później, przy okazji omawiania klas złożoności obliczeniowej.

Definicja

Język rozpoznawany przez niedeterministyczną maszynę Turinga $NMT$ jest to zbiór

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L(\mathbf{NMT})=\left\{ w\in \Sigma _{T}^{*}\: :\: \sharp s_{0}w\sharp \mapsto^{*}\sharp w_{1}s_{F}w_{2}\sharp ,\; dla\: pewnych\: w_{1},w_{2}\in \Sigma _{T}^{*},s_{F}\in S_{F}\right\} .}

Język $L\subset {\mathrm{\Sigma }}_I^{*}$ jest rozpoznawany (akceptowany) przez niedeterministyczną maszynę Turinga, jeśli istnieje ${𝒩}{ℳ}{𝒯}$ taka, że $L({𝒩}{ℳ}{𝒯})=L.$

Podkreślamy fakt, że aby maszyna niedeterministyczna zaakceptowała słowo wejściowe wystarczy aby wśród wszystkich możliwych obliczeń znalazło się co najmniej jedno akceptujące.

Wprost z definicji wynika że każda maszyna deterministyczna jest także maszyną niedeterministyczną, co oznacza że języki rozpoznawane przez maszyny deterministyczne są zawarte w klasie języków rozpoznawanych przez maszyny niedeterministyczne. Przeciwna inkluzja jest gwarantowana przez następujące twierdzenie.

Twierdzenie

Dla każdej niedeterministycznej maszyny Turinga ${𝒩}{ℳ}{𝒯}$ istnieje maszyna deterministyczna ${ℳ}{𝒯}$ taka, że

$L({𝒩}{ℳ}{𝒯})=L({ℳ}{𝒯})$

Dowód

(Szkic). Aby sprawdzić czy maszyna niedeterministyczna akceptuje dane słowo wejściowe należy przejrzeć wszystkie możliwe obliczenia wykonywane, tworzące drzewo obliczeń. Poziomy drzewa tworzone są przez kroki czasowe, wierzchołki stanowią obliczenia wykonane w danym kroku czasowym a gałęzie zadane są przez relację bezpośredniego następstwa. W celu sprawdzenia czy maszyna akceptuje dane słowo przeglądamy drzewo obliczeń poziomami (por. algorytm BFS) i akceptujemy gdy przeglądana konfiguracja była akceptująca. Tą techniką przeglądamy wszystkie możliwe obliczenia wykonane w $1,2,3,\dots$ krokach.

Do dokonania symulacji najwygodniej jest użyć maszyny $3$-głowicowej z możliwością czytania na wszystkich taśmach. Wprowadzamy te taśmy kolejno do przechowywania słowa wejściowego, symulacji działania maszyny niedeterministycznej i adresowania wyboru przejść ze zbioru przejść danego przez funkcję przejść. Symulacja przebiega w czterech krokach:

1. Rozpocznij ze słowem wejściowym $w$ na taśmie $1$ oraz pustymi

taśmami $2$ i $3$.

1. Przekopiuj taśmę $1$ na taśmę $2$.
2. Użyj taśmy $2$ do symulacji $w$ wykorzystując taśmę $3$ do

wyboru przejść funkcji przejść $f$. Jeśli po wykonaniu skończonego zbioru instrukcji według adresowania z taśmy $3$ otrzymano konfigurację akceptującą to akceptuj. W przeciwnym razie przejdź do następnego punktu.

1. Zamień ciąg adresowy na następny w kolejności

leksykograficznej. Jeśli zapisany ciąg jest ostatnim możliwym ciągiem adresowym o długości $N$ zapisz na taśmie $3$ pierwszy w kolejności leksykograficznej ciąg adresowy o długości $N+1$ oraz przejdź do $2$.

Wniosek

Dla każdej maszyny Turinga ${ℳ}{𝒯}$ istnieje maszyna Turinga ${{ℳ}{𝒯}}^{\prime }$ taka że

$L({ℳ}{𝒯})=L({{ℳ}{𝒯}}^{\prime })$

oraz dla każdego $w\in L({{ℳ}{𝒯}}^{\prime })$ maszyna ${{ℳ}{𝒯}}^{\prime }$ zatrzymuje się na $w$.

Dowód

Wystarczy przerobić maszynę ${ℳ}{𝒯}$ na maszynę niedeterministyczną ${𝒩}{ℳ}{𝒯}$ posiadającą dodatkowy stan $s_A$ oraz taką że dla każdego stanu ze zbioru $S_F$ pod wpływem dowolnego symbolu z ${\mathrm{\Sigma }}_T$ maszyna ${𝒩}{ℳ}{𝒯}$ posiada dodatkowe przejście do $s_A$ w którym już pozostaje i nic nie zmienia. Jasno widać, że $L({ℳ}{𝒯})=L({𝒩}{ℳ}{𝒯})$.

Twierdzenie [[##TwND=D|Uzupelnic TwND=D|]] pozwala na otrzymanie maszyny ${{ℳ}{𝒯}}^{\prime }$ akceptującej ten sam język co ${𝒩}{ℳ}{𝒯}$ z dodatkowym założeniem, że gdy ${𝒩}{ℳ}{𝒯}$ osiąga stan $s_A$ maszyna ${{ℳ}{𝒯}}^{\prime }$ się zatrzymuje. Zauważmy że stan $s_A$ można osiągnąć tylko dla słów akceptowanych prze ${𝒩}{ℳ}{𝒯}$ a z drugiej strony każde słowo akceptowane przez ${𝒩}{ℳ}{𝒯}$ prowadzi do conajmniej jednego obliczenia kończącego się w $s_A$.