Teoria obliczeń

9. Teoria obliczeń#

9.1. Wprowadzenie#

Narration

Automat skończony to matematyczny model urządzenia (lub algorytmu decyzyjnego), które w każdej chwili znajduje się w jednym z skończenie wielu stanów i zmienia stan pod wpływem kolejnego odczytanego symbolu wejściowego.

Modele tego typu opisują wiele urządzeń technicznych, np.:

  • automatyczne drzwi

  • automaty sprzedające napoje

  • windę

  • sygnalizację świetlną

  • proste sterowniki taśmy produkcyjnej

  • parsery leksykalne w kompilatorach

W tym wykładzie omówimy automaty deterministyczne i niedeterministyczne, język, który taki automat rozpoznaje, wyrażenia regularne opisujące te języki, a na koniec dwa istotne uogólnienia: maszynę Turinga (model dowolnego algorytmu) oraz sieć Petriego (model systemów współbieżnych).

9.2. Alfabety, słowa i języki#

Definicja 9.1

Alfabetem nazywamy dowolny, niepusty, skończony zbiór symboli, oznaczany zazwyczaj przez \(A .\)

Przykład 9.1

Przykłady alfabetów:

  1. alfabet liter łacińskich

  2. alfabet cyfr arabskich

  3. \(A = \Set{0,1}\)

Definicja 9.2

Słowem nad alfabetem \(A\) nazywamy dowolny skończony ciąg elementów zbioru \(A\), np. \(w = w_1 w_2 \cdots w_n\), gdzie \(w_i \in A .\)

Słowem pustym , oznaczanym \(\varepsilon\), nazywamy słowo niezawierające żadnego symbolu.

Zbiór wszystkich słów nad alfabetem \(A\) oznaczamy przez \(A^*\) .

Definicja 9.3

Językiem nad alfabetem \(A\) nazywamy dowolny podzbiór \(L \subseteq A^* .\)

Przykład 9.2

Dla alfabetu \(A = \Set{0,1}\) przykładowymi językami są:

  1. \(L_1 = \Set{\varepsilon, 0, 00, 000, \ldots}\) – słowa złożone z samych zer

  2. \(L_2 = \Set{w \in A^* : w \text{ ma parzystą liczbę jedynek}}\)

  3. \(L_3 = A^*\) – wszystkie słowa nad \(A\)

9.3. Deterministyczny automat skończony#

Narration

Ustalmy alfabet wejściowy \(A .\) Automat skończony przetwarza słowo symbol po symbolu, startując w ustalonym stanie początkowym i przechodząc między stanami zgodnie z odczytywanymi symbolami.

Definicja 9.4

Deterministycznym automatem skończonym (w skrócie DFA ) nazywamy piątkę

\[\mathcal A = (X, A, \delta, x_0, F),\]

gdzie:

  • \(X\) – skończony zbiór stanów ,

  • \(A\) – alfabet wejściowy ,

  • \(\delta \colon X \times A \to X\) – funkcja przejścia ,

  • \(x_0 \in X\) – stan początkowy ,

  • \(F \subseteq X\) – zbiór stanów końcowych (akceptujących) .

Uwaga 9.1

Automat skończony można sobie wyobrazić jako taśmę, na której zapisane jest słowo wejściowe, oraz głowicę przesuwającą się po taśmie w prawo, sterowaną funkcją \(\delta\): będąc w stanie \(x\) i czytając symbol \(a\), głowica przechodzi do stanu \(\delta(x,a)\) i przesuwa się o jedno pole w prawo.

Definicja 9.5

Rozszerzoną funkcję przejścia \(\hat\delta \colon X \times A^* \to X\) definiujemy indukcyjnie:

\[\begin{split}\begin{aligned} \hat\delta(x, \varepsilon) & = x, \\ \hat\delta(x, wa) & = \delta(\hat\delta(x,w), a) \qquad \text{dla } w \in A^*,\ a \in A. \end{aligned}\end{split}\]

Innymi słowy, \(\hat\delta(x,w)\) to stan, w jakim znajdzie się automat po przeczytaniu, startując ze stanu \(x\), całego słowa \(w .\)

Słowo \(w \in A^*\) jest akceptowane przez automat \(\mathcal A\), jeśli \(\hat\delta(x_0, w) \in F .\)

Językiem rozpoznawanym (generowanym) przez automat \(\mathcal A\) nazywamy zbiór

\[L(\mathcal A) = \Set{w \in A^* : \hat\delta(x_0, w) \in F}.\]

Przykład 9.3

Rozważmy automat \(\mathcal A = (X,A,\delta,x_0,F)\) z \(A = \Set{0,1}\), \(X = \Set{x_0, x_1}\), \(F = \Set{x_0}\), sprawdzający parzystość liczby jedynek w słowie:

stan

0

1

\(x_0\)

\(x_0\)

\(x_1\)

\(x_1\)

\(x_1\)

\(x_0\)

Stan \(x_0\) oznacza „dotychczas przeczytano parzystą liczbę jedynek”, \(x_1\) – „nieparzystą”. Ponieważ \(F = \Set{x_0}\), to

\[L(\mathcal A) = \Set{w \in \Set{0,1}^* : w \text{ ma parzystą liczbę jedynek}}.\]

Ćwiczenie 9.1

Dla automatu z powyższego przykładu sprawdźmy krok po kroku, czy słowa \(w_1 = 1101\) oraz \(w_2 = 110011\) są akceptowane.

Rozwiązanie

Śledzimy kolejne stany, startując z \(x_0\):

  • \(w_1 = 1101\): \(\ x_0 \xrightarrow{1} x_1 \xrightarrow{1} x_0 \xrightarrow{0} x_0 \xrightarrow{1} x_1 .\)

    Kończymy w \(x_1 \notin F\), więc \(w_1\) nie jest akceptowane (rzeczywiście, \(w_1\) ma trzy jedynki – liczbę nieparzystą).

  • \(w_2 = 110011\): \(\ x_0 \xrightarrow{1} x_1 \xrightarrow{1} x_0 \xrightarrow{0} x_0 \xrightarrow{0} x_0 \xrightarrow{1} x_1 \xrightarrow{1} x_0 .\)

    Kończymy w \(x_0 \in F\), więc \(w_2\) jest akceptowane (\(w_2\) ma cztery jedynki – liczbę parzystą).

9.4. Automat niedeterministyczny#

Narration

W automacie deterministycznym każdy stan i symbol jednoznacznie wyznaczają kolejny stan. W wielu zastosowaniach wygodniej jest dopuścić, by z danego stanu, po przeczytaniu tego samego symbolu, automat mógł przejść do kilku różnych stanów jednocześnie (lub do żadnego) – tak jakby „zgadywał” najlepszą kontynuację.

Definicja 9.6

Niedeterministycznym automatem skończonym (w skrócie NFA ) nazywamy piątkę \(\mathcal A = (X,A,\delta,x_0,F)\), w której – w odróżnieniu od DFA – funkcja przejścia ma postać

\[\delta \colon X \times A \to 2^X,\]

tzn. każdej parze (stan, symbol) przyporządkowuje zbiór możliwych stanów następnych.

Słowo \(w = w_1 \cdots w_n \in A^*\) jest akceptowane przez \(\mathcal A\), jeśli istnieje ciąg stanów \(x_1, \ldots, x_n \in X\) taki, że \(x_n \in F\) oraz

\[x_0 \xrightarrow{w_1} x_1 \xrightarrow{w_2} x_2 \xrightarrow{w_3} \cdots \xrightarrow{w_n} x_n, \qquad \text{gdzie } x_{i} \in \delta(x_{i-1}, w_i).\]

Innymi słowy, wystarczy, że istnieje choć jedna ścieżka obliczenia prowadząca do stanu akceptującego.

Przykład 9.4

Zbudujmy NFA rozpoznający język słów nad \(A=\Set{0,1}\) zawierających podsłowo \(11\). Niech \(X = \Set{x_0,x_1,x_2}\), \(F = \Set{x_2}\):

stan

0

1

\(x_0\)

\(\Set{x_0}\)

\(\Set{x_0,\ x_1}\)

\(x_1\)

\(\Set{x_0}\)

\(\Set{x_2}\)

\(x_2\)

\(\Set{x_2}\)

\(\Set{x_2}\)

Kluczowy jest przypadek \(\delta(x_0,1) = \Set{x_0,x_1}\): czytając jedynkę w stanie \(x_0\), automat jednocześnie rozważa dwie możliwości – że ta jedynka jest nieistotna (zostaje w \(x_0\)) oraz że jest to pierwsza jedynka szukanego podsłowa \(11\) (przechodzi do \(x_1\)). Taka „równoległa” decyzja nie ma odpowiednika w automacie deterministycznym.

Ćwiczenie 9.2

Sprawdźmy, czy powyższy automat akceptuje słowo \(w=10110\), wskazując odpowiednią ścieżkę obliczenia.

Rozwiązanie

Szukamy ścieżki kończącej się w \(x_2 .\) Wybierzmy przejścia:

\[x_0 \xrightarrow{1} x_1 \xrightarrow{0} x_0 \xrightarrow{1} x_1 \xrightarrow{1} x_2 \xrightarrow{0} x_2.\]

Ostatni stan \(x_2 \in F\), więc słowo \(10110\) jest akceptowane (rzeczywiście zawiera podsłowo \(11\) na pozycjach 3–4).

Twierdzenie 9.1

Dla każdego automatu niedeterministycznego \(\mathcal A\) istnieje automat deterministyczny \(\mathcal A'\) taki, że \(L(\mathcal A) = L(\mathcal A')\) (i odwrotnie – każdy DFA jest szczególnym przypadkiem NFA).

Uwaga 9.2

Dowód konstruktywny powyższego twierdzenia (konstrukcja podzbiorowa ) polega na przyjęciu za stany nowego automatu podzbiorów zbioru stanów \(X\): nowy stan \(x_0'\) to \(\Set{x_0}\), a \(\delta'(S,a) = \bigcup_{x\in S}\delta(x,a)\) dla \(S \subseteq X .\) Zbiór stanów nowego automatu może mieć aż \(2^{|X|}\) elementów, ale mimo tego wzrostu rozmiaru moc wyrażania obu typów automatów jest identyczna.

9.5. Języki regularne#

Definicja 9.7

Językiem regularnym nazywamy język rozpoznawany przez pewien automat skończony (deterministyczny, równoważnie – niedeterministyczny).

Narration

Języki regularne są zamknięte (m.in.) ze względu na następujące operacje. Dla języków \(L_1, L_2 \subseteq A^*\):

Definicja 9.8

Konkatenacją języków \(L_1, L_2\) nazywamy język

\[L_1 L_2 = \Set{uv : u \in L_1,\ v \in L_2}.\]

Domknięciem Kleenego języka \(L\) nazywamy język

\[L^* = \bigcup_{k=0}^{\infty} L^k, \qquad \text{gdzie } L^0 = \Set{\varepsilon}, \quad L^{k+1} = L^k L.\]

Uwaga 9.3

Jeśli \(L_1, L_2\) są regularne, to regularne są także \(L_1 \cup L_2\), \(L_1 L_2\) oraz \(L_1^*\) (a także \(L_1 \cap L_2\) i \(A^* \setminus L_1\)).

Przykład 9.5

Dla \(L_1=\Set{a}\), \(L_2=\Set{b}\), \(L_3=\Set{c}\):

\[\begin{split}\begin{aligned} L_1\cup L_2L_3^* & =\Set{a,\ b,\ bc,\ bcc,\ bccc,\ldots}, \\ L_1^* & =\Set{\varepsilon,a,aa,aaa,\ldots}. \end{aligned}\end{split}\]

9.6. Wyrażenia regularne#

Definicja 9.9

Wyrażeniem regularnym nad alfabetem \(A\) nazywamy ciąg znaków zbudowany z symboli alfabetu \(A\), symboli \(\emptyset,\ \varepsilon,\ +,\ ^*,\ (,\ )\), o jednej z poniższych postaci:

  • \(\emptyset\) lub \(\varepsilon\),

  • \(a\), gdzie \(a \in A\),

  • jeśli \(r, s\) są wyrażeniami regularnymi, to wyrażeniami regularnymi są również \(r+s\), \(\;rs\;\) oraz \(r^* .\)

Definicja 9.10

Każde wyrażenie regularne \(r\) definiuje język \(L_r \subseteq A^*\), zgodnie z regułami:

\[\begin{aligned} \emptyset & \rightsquigarrow \emptyset, & \varepsilon & \rightsquigarrow \Set{\varepsilon}, & a\in A & \rightsquigarrow \Set{a}, \end{aligned}\]

a jeśli \(r,s\) definiują odpowiednio \(L_r, L_s\), to:

\[\begin{aligned} r+s & \rightsquigarrow L_r \cup L_s, & rs & \rightsquigarrow L_r L_s, & r^* & \rightsquigarrow L_r^*. \end{aligned}\]

Przykład 9.6

Dla \(A = \Set{0,1}\):

\[\begin{split}\begin{aligned} 0 & \rightsquigarrow \Set{0}, & 0+1 & \rightsquigarrow \Set{0,1}, & (0+1)0 & \rightsquigarrow \Set{00,10}, \\ 0^* & \rightsquigarrow \Set{\varepsilon,0,00,000,\ldots}, & 10^*(11) & \rightsquigarrow \Set{111,\ 1011,\ 10011,\ 100011,\ldots}. \end{aligned}\end{split}\]

Wyrażenie \((0+1)^*11(0+1)^*\) definiuje dokładnie język słów zawierających podsłowo \(11\), czyli język rozpoznawany przez automat z Prz. 9.4.

Twierdzenie 9.2

Twierdzenie Kleenego. Dla języka \(L \subseteq A^*\) następujące warunki są równoważne:

  1. \(L\) jest językiem regularnym.

  2. \(L\) jest rozpoznawany przez pewien automat deterministyczny.

  3. \(L\) jest rozpoznawany przez pewien automat niedeterministyczny.

  4. Istnieje wyrażenie regularne definiujące \(L .\)

Ćwiczenie 9.3

Napiszmy wyrażenie regularne nad \(A=\Set{0,1}\) opisujące język słów, które kończą się na \(01\).

Rozwiązanie

Przed końcówką \(01\) może wystąpić dowolny, w tym pusty, ciąg symboli z \(A\), więc szukanym wyrażeniem jest

\[(0+1)^*01.\]

9.7. Maszyna Turinga#

Narration

Automaty skończone mają istotne ograniczenie: dysponują jedynie skończoną pamięcią zakodowaną w bieżącym stanie i nie mogą np. porównać liczby zer z liczbą jedynek w dowolnie długim słowie (rozstrzygnąć, czy słowo należy do \(\Set{0^n1^n : n\geq 0}\)). Aby modelować dowolne algorytmy, Alan Turing zaproponował automat wyposażony w nieograniczoną, jednostronnie lub dwustronnie nieskończoną taśmę roboczą.

Definicja 9.11

Maszyną Turinga nazywamy szóstkę

\[M = (Q,\ A,\ \Gamma,\ \delta,\ q_0,\ F),\]

gdzie:

  • \(Q\) – skończony zbiór stanów,

  • \(A\) – alfabet wejściowy,

  • \(\Gamma \supseteq A\) – alfabet taśmowy , zawierający dodatkowo symbol pusty \(\sqcup \in \Gamma\setminus A\),

  • \(\delta \colon Q \times \Gamma \to Q \times \Gamma \times \Set{L,P}\) – funkcja przejścia (częściowa): w stanie \(q\), czytając symbol \(a\), maszyna zapisuje nowy symbol, przechodzi do nowego stanu i przesuwa głowicę o jedno pole w Lewo lub Prawo,

  • \(q_0 \in Q\) – stan początkowy,

  • \(F \subseteq Q\) – zbiór stanów akceptujących.

Definicja 9.12

Konfiguracją maszyny \(M\) nazywamy opis całej sytuacji obliczenia: zawartość taśmy, pozycję głowicy oraz bieżący stan. Pojedynczy krok obliczenia (zgodny z \(\delta\)) przekształca jedną konfigurację w drugą.

Słowo \(w \in A^*\) jest akceptowane przez \(M\), jeśli startując z konfiguracji początkowej (taśma zawiera \(w\), głowica na pierwszym symbolu, stan \(q_0\)), maszyna po skończonej liczbie kroków osiąga stan \(q \in F .\)

Uwaga 9.4

W odróżnieniu od automatu skończonego, maszyna Turinga może:

  • wielokrotnie wracać do już odczytanych fragmentów taśmy (ruch w lewo),

  • nadpisywać taśmę, wykorzystując ją jako pamięć roboczą,

  • nie zatrzymać się nigdy dla pewnych danych wejściowych.

Teza Churcha–Turinga (nie jest twierdzeniem matematycznym, lecz przyjmowanym założeniem) głosi, że każdy intuicyjnie obliczalny algorytm można zrealizować za pomocą pewnej maszyny Turinga. Z tego powodu maszyna Turinga jest powszechnie przyjmowanym formalnym odpowiednikiem pojęcia „algorytmu”.

Przykład 9.7

Opiszmy (nieformalnie, bez pełnej tabeli przejść) maszynę Turinga rozpoznającą język \(L = \Set{0^n1^n : n \geq 0}\), którego – jak wspomniano wyżej – żaden automat skończony nie rozpoznaje:

  1. Jeśli taśma jest pusta, akceptuj (przypadek \(n=0\)).

  2. Skreśl (zamień na symbol pomocniczy \(X\)) skrajnie lewe \(0 .\)

  3. Przesuwaj głowicę w prawo, aż napotkasz skrajnie lewą, nieskreśloną jedynkę; skreśl ją (na \(Y\)).

  4. Wróć głowicą w lewo aż do skrajnie lewego nieskreślonego \(0\) i powtórz kroki 2–3.

  5. Gdy po kroku 2 nie ma już żadnego nieskreślonego \(0\): sprawdź, czy na taśmie nie zostały nieskreślone jedynki – jeśli nie, akceptuj; jeśli tak (lub napotkano \(0\) zamiast \(1\) w kroku 3), odrzuć.

Ten algorytm parami „kasuje” kolejne zera i jedynki, więc akceptuje dokładnie słowa z równą liczbą zer (na początku) i jedynek (na końcu).