--- title: "Teoria obliczeń" lecture_number: 8 has_solutions: true has_exercises: true --- ```{include} ../_includes/sagecell-loader.md ``` # Teoria obliczeń ## Wprowadzenie ::::{narration} **Automat skończony** {index}`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.: :::{container} columns-2-auto - 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). :::: ## Alfabety, słowa i języki :::{prf:definition} **Alfabetem** {index}`alfabet` nazywamy dowolny, niepusty, skończony zbiór symboli, oznaczany zazwyczaj przez $A .$ ::: :::{prf:example} Przykłady alfabetów: 1. alfabet liter łacińskich 2. alfabet cyfr arabskich 3. $A = \Set{0,1}$ ::: :::{prf:definition} **Słowem** {index}`słowo` 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** {index}`słowo; puste`, oznaczanym $\varepsilon$, nazywamy słowo niezawierające żadnego symbolu. Zbiór wszystkich słów nad alfabetem $A$ oznaczamy przez $A^*$ {index}`słowo; zbiór wszystkich słów`. ::: :::{prf:definition} **Językiem** {index}`język` nad alfabetem $A$ nazywamy dowolny podzbiór $L \subseteq A^* .$ ::: :::{prf:example} 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$ ::: ## 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. ::: :::{prf:definition} **Deterministycznym automatem skończonym** {index}`automat skończony; deterministyczny` (w skrócie **DFA** {index}`DFA`) nazywamy piątkę ```{math} \mathcal A = (X, A, \delta, x_0, F), ``` gdzie: - $X$ -- skończony zbiór **stanów** {index}`automat skończony; stan`, - $A$ -- **alfabet wejściowy** {index}`automat skończony; alfabet wejściowy`, - $\delta \colon X \times A \to X$ -- **funkcja przejścia** {index}`automat skończony; funkcja przejścia`, - $x_0 \in X$ -- **stan początkowy** {index}`automat skończony; stan początkowy`, - $F \subseteq X$ -- zbiór **stanów końcowych (akceptujących)** {index}`automat skończony; stan końcowy`. ::: :::{prf:remark} 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. ::: :::{prf:definition} Rozszerzoną funkcję przejścia $\hat\delta \colon X \times A^* \to X$ definiujemy indukcyjnie: ```{math} \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} ``` 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** {index}`automat skończony; słowo akceptowane` przez automat $\mathcal A$, jeśli $\hat\delta(x_0, w) \in F .$ **Językiem rozpoznawanym (generowanym)** {index}`automat skończony; język rozpoznawany` przez automat $\mathcal A$ nazywamy zbiór ```{math} L(\mathcal A) = \Set{w \in A^* : \hat\delta(x_0, w) \in F}. ``` ::: :::{prf:example} 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: :::{list-table} :class: table-auto-width :header-rows: 1 :widths: 15 15 15 * - 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 ```{math} L(\mathcal A) = \Set{w \in \Set{0,1}^* : w \text{ ma parzystą liczbę jedynek}}. ``` ::: ::::{exercise} :label: m-mat1-lec-08-ex-01 :class: [exercise] Dla automatu z powyższego przykładu sprawdźmy krok po kroku, czy słowa $w_1 = 1101$ oraz $w_2 = 110011$ są akceptowane. :::: :::{solution-without-reference} :class: [solution] dropdown Ś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ą). ::: ## 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ę. ::: :::{prf:definition} **Niedeterministycznym automatem skończonym** {index}`automat skończony; niedeterministyczny` (w skrócie **NFA** {index}`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ć ```{math} \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 ```{math} 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. ::: :::{prf:example} :label: example-nfa-11 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}$: :::{list-table} :class: table-auto-width :header-rows: 1 :widths: 15 20 20 * - 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. ::: ::::{exercise} :label: m-mat1-lec-08-ex-02 :class: [exercise] Sprawdźmy, czy powyższy automat akceptuje słowo $w=10110$, wskazując odpowiednią ścieżkę obliczenia. :::: :::{solution-without-reference} :class: [solution] dropdown Szukamy ścieżki kończącej się w $x_2 .$ Wybierzmy przejścia: ```{math} 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). ::: :::{prf:theorem} 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). ::: :::{prf:remark} Dowód konstruktywny powyższego twierdzenia (**konstrukcja podzbiorowa** {index}`automat skończony; 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. ::: ## Języki regularne :::{prf:definition} **Językiem regularnym** {index}`język; regularny` 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^*$: ::: :::{prf:definition} **Konkatenacją** {index}`język; konkatenacja` języków $L_1, L_2$ nazywamy język ```{math} L_1 L_2 = \Set{uv : u \in L_1,\ v \in L_2}. ``` **Domknięciem Kleenego** {index}`język; domknięcie Kleenego` języka $L$ nazywamy język ```{math} L^* = \bigcup_{k=0}^{\infty} L^k, \qquad \text{gdzie } L^0 = \Set{\varepsilon}, \quad L^{k+1} = L^k L. ``` ::: :::{prf:remark} 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$). ::: :::{prf:example} Dla $L_1=\Set{a}$, $L_2=\Set{b}$, $L_3=\Set{c}$: ```{math} \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} ``` ::: ## Wyrażenia regularne :::{prf:definition} **Wyrażeniem regularnym** {index}`wyrażenie regularne` 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^* .$ ::: :::{prf:definition} Każde wyrażenie regularne $r$ **definiuje** {index}`wyrażenie regularne; definiowany język` język $L_r \subseteq A^*$, zgodnie z regułami: ```{math} \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: ```{math} \begin{aligned} r+s & \rightsquigarrow L_r \cup L_s, & rs & \rightsquigarrow L_r L_s, & r^* & \rightsquigarrow L_r^*. \end{aligned} ``` ::: :::{prf:example} Dla $A = \Set{0,1}$: ```{math} \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} ``` 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 {prf:ref}`example-nfa-11`. ::: :::{prf:theorem} :label: thm-kleene **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 .$ ::: ::::{exercise} :label: m-mat1-lec-08-ex-03 :class: [exercise] Napiszmy wyrażenie regularne nad $A=\Set{0,1}$ opisujące język słów, które **kończą się na $01$**. :::: :::{solution-without-reference} :class: [solution] dropdown Przed końcówką $01$ może wystąpić dowolny, w tym pusty, ciąg symboli z $A$, więc szukanym wyrażeniem jest ```{math} (0+1)^*01. ``` ::: ## 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ą**. ::: :::{prf:definition} **Maszyną Turinga** {index}`maszyna Turinga` nazywamy szóstkę ```{math} 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** {index}`maszyna Turinga; 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. ::: :::{prf:definition} **Konfiguracją** {index}`maszyna Turinga; konfiguracja` 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 .$ ::: :::{prf:remark} 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** {index}`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". ::: :::{prf:example} 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). :::