Deterministyczne automaty skończone

Wstęp

Przypomnijmy, że na język można patrzeć jak na problem decyzyjny. W ramach tego wykładu zajmiemy się modelowaniem takich mechanizmów liczących, które są przystosowane do rozstrzygania, czy dane słowo należy do języka i są wyposażone w pomocniczą pamięć stałej wielkości. Takie modele to właśnie automaty skończone. Języki, dla których takie mechanizmy istnieją, jak się później okaże, to języki regularne. Zacznijmy jednak od ustalenia pewnych, być może oczywistych i intuicyjnych pojęć.

Intuicje

Ustalmy najpierw pewne intuicyjne pojęcia: stanu i przejścia. Stan jakiegokolwiek systemu (czy mechanizmu), to pełna informacja na jego temat w danym momencie czasu. W szczególności stan zawiera wszelką ,,pamięć'' w jaką wyposażony jest dany system. Również wszystko to co zdarzyło się do danego momentu ma wpływ na przyszłość tylko o tyle, o ile wpłynęło na stan systemu w danej chwili.

Będziemy rozpatrywać takie systemy i mechanizmy, których stan zmienia się w sposób dyskretny (tj. skokowy), a nie ciągły. Podejście takie ma zastosowanie np. do komputerów i urządzeń cyfrowych. Praca podzespołów komputerowych jest taktowana odpowiednimi zegarami. Ich stan może się zmieniać tylko wraz z kolejnymi taktami odpowiednich zegarów. Na cały komputer możemy spojrzeć jak na system, w którym czas biegnie nie w sposób ciągły, ale drobnymi skokami. W przypadku wielu innych systemów takie podejście też może być poprawne, jeżeli ich stan, który będzie nas interesował, będzie miał charakter dyskretny. Wówczas jego zmiany będą musiały mieć charakter skokowy. Dlatego też w naszych modelach czas będzie dyskretny, tzn. będzie on płynął drobnymi kroczkami.

Zmianę stanu będziemy nazywać przejściem -- od stanu w chwili poprzedniej do stanu w chwili następnej. Zwykle przejście ma miejsce jako reakcja na pewne zdarzenie. Założymy przy tym, że przejścia są natychmiastowe -- jest to oczywiście uproszczenie, tak samo jak założenie, że czas jest dyskretny.

Najlepiej powyższe intuicje zilustrować na przykładach:

• Kostka Rubik'a -- jej stany to możliwe ułożenia, a przejścia zachodzą na skutek wykonywania pojedynczych ruchów.
• Zegarek cyfrowy -- Stan zegarka to aktualny czas (z dokładnością do jego pomiaru przez zegarek) oraz cała pamięć zegarka (np. godzina, na którą ustawiony jest budzik). Przejścia zachodzą na skutek upływu czasu lub naciskania przycisków zegarka.
• Sterownik windy -- stany tego sterownika zawierają informację m.inn. nt. położenia windy (z pewną dokładnością), kierunku jej jazdy, otwarcia lub zamknięcia drzwi, oraz tego, jakie guziki (w windzie i na zewnątrz) były naciśnięte.
• Wszechświat(?) -- pytanie czy wszechświat jest systemem dyskretnym pozostawimy filozofom i fizykom.

Przykład

Na poniższym diagramie przedstawiono uproszczony schemat działania bardzo prostego odtwarzacza video. Stany zaznaczono owalami. W momencie włączenia system znajduje się w stanie ,,Empty''. Przejścia przedstawiono jako strzałki i umieszczono przy nich etykiety reprezentujące zdarzenia powodujące określone przejścia.

Deterministyczne automaty skończone

Powróćmy do języków. Interesuje nas modelowanie mechanizmów obliczeniowych odpowiadających na pytanie, czy dane słowo należy do ustalonego języka. Automat skończony wczytuje dane słowo znak po znaku i po wczytaniu całego słowa udziela odpowiedzi, czy słowo to należy do ustalonego języka. Przejścia między stanami zachodzą w automacie skończonym na skutek wczytywania kolejnych znaków analizowanego słowa. W automacie deterministycznym, dla każdego znaku jaki może się pojawić na wejściu i dla każdego stanu automatu, ze stanu tego wychodzi dokładnie jedno przejście odpowiadające danemu znakowi -- w każdej sytuacji działanie automatu musi być określone jednoznacznie. (W tym wykładzie będziemy się zajmować wyłącznie automatami deterministycznymi. Automaty niedeterministyczne pojawią się w kolejnym wykładzie i dopiero wówczas będziemy je odróżniać.)

To, jaka jest odpowiedź udzielana przez automat zależy od stanu osiąganego po wczytaniu całego słowa. Jeżeli odpowiedź jest pozytywna, to mówimy, że automat akceptuje słowo, a w przeciwnym przypadku mówimy, że je odrzuca. Stany, w których automat akceptuje nazywamy stanami akceptującymi. Pamiętajmy jednak, że o tym, czy automat akceptuje słowo decyduje wyłącznie ostatni stan -- ten, w którym automat jest po wczytaniu całego słowa.

Dodatkowo, automat skończony, jak sama nazwa wskazuje, ma skończoną liczbę stanów. Oznacza to, że dysponuje on stałą pamięcią dodatkową, tzn. wielkość pamięci dodatkowej nie zależy od długości wczytywanego słowa i jest ograniczona przez stałą. Jeżeli do stwierdzenia, czy słowo należy do ustalonego języka potrzebna jest pamięć pomocnicza, której nie da się ograniczyć przez stałą, to taki język nie jest akceptowany przez żaden automat skończony. Przykłady takich języków, oraz techniki dowodzenia tego poznamy w dalszych wykładach.

Przykład

Zanim podamy formalną definicję automatu skończonego zobaczmy prosty przykład takiego automatu.

Do prezentowania automatów skończonych będziemy używać diagramów podobnych do diagramu odtwarzacza wideo z poprzedniego punktu. Stany automatu oznaczamy na diagramie punktami, a przejścia strzałkami. Przejścia etykietujemy znakami, których wczytanie powoduje dane przejście. Początkowy stan automatu oznaczamy strzałką ,,znikąd''. Stany akceptujące zaznaczamy otaczając je dodatkowym kółkiem.

 

Powyższy automat wczytuje słowa nad alfabetem $\Sigma=\{a,b\}$. Akceptuje on wszystkie słowa zawierające choć jedną literę a -- tylko takie słowa mogą spowodować przejście do stanu po prawej stronie.

Definicja

Automat skończony (deterministyczny) M, to dowolna taka piątka $M = \angles{Q, \Sigma, \delta, s, F}$, w której:

• Q to skończony zbiór stanów, $\Sigma$ to (skończony) alfabet wejściowy, $\delta: Q \times \Sigma \to Q$ to funkcja przejścia -- $\delta(q, a)$ to stan do którego przechodzimy ze stanu q na skutek wczytania znaku a, s to stan początkowy, $F \subseteq Q$ to zbiór stanów akceptujących.

Przedstawiając automat musimy podać informacje o wszystkich pięciu elementach. Formalne podawanie piątki, takiej jak w definicji, jest mało czytelne. Dlatego też zwykle przedstawia się automat w postaci tabelki lub diagramu.

Przykład

Następująca diagram i tabelka przedstawiają ten sam automat.

$$\begin{array}{ll\vert cc} & & a & b \\ \hline \to & 0 &... ...\ & 1 & 2 & 1\\ & 2 & 3 & 2 \\ F& 3 & 3 & 3 \end{array}$$

Tabelka przedstawia przede wszystkim funkcję przejścia $\delta$. Wiersze są indeksowane stanami. Kolumny są indeksowane znakami z alfabetu wejściowego. Komórki tabeli zawierają stany, do których przechodzimy na skutek wczytania pojedynczych znaków. Dodatkowo, stan początkowy jest zaznaczony za pomocą strzałki $\to$, a stany akceptujące są zaznaczone literami F.

Zaletą diagramów jest ich przejrzystość oraz to, że nie ma konieczności nazywania stanów. Natomiast zaletą tabel jest ich zwarta postać.

Dane dla automatu to dowolne słowo $x \in \Sigma^*$. Działanie automatu możemy zasymulować w następujący sposób:

1. Na początku automat jest w stanie początkowym.Wczytujemy kolejne znaki słowa na wejściu i zmieniamy stan zgodnie z przejściami odpowiadającymi tym znakom.Po wczytaniu całego słowa i wykonaniu wszystkich przejść sprawdzamy, czy automat jest w stanie akceptującym. Jeżeli tak, to słowo jest akceptowane przez automat, wpp. nie.

Mając automat przedstawiony w formie diagramu możemy potraktować ten diagram jak planszę. Na początku stawiamy pionek na polu / w stanie początkowym. Następnie przesuwamy pionek zgodnie z wczytywanymi znakami. Jeśli na koniec jesteśmy na polu / w stanie akceptującym, to słowo jest akceptowane.

Przykład

 

 

Czas formalnie zdefiniować działanie deterministycznych automatów skończonych. Niech $M = \angles{Q, \Sigma, \delta, s, F}$ będzie ustalonym deterministycznym automatem skończonym.

Definicja

Funkcję przejścia $\delta: Q \times \Sigma \to Q$ rozszerzamy do funkcji $\delta^*: Q \times \Sigma^* \to Q$ w następujący sposób:

$$\delta^* (q, \varepsilon) = q$$

$$\delta^* (q, xa) = \delta(\delta^*(q, x), a)$$

Podczas gdy funkcja $\delta$ określa działanie automatu dla pojedynczego znaku, funkcja $\delta^*$ określa jego działanie dla całych słów.

Definicja

Automat akceptuje słowo x wtw., gdy $\delta^*(s, x) \in F$.
Język akceptowany przez automat M, to:

$$L(M) \equiv \{ x \in \Sigma^* : \delta^* (s, x) \in F \}$$

Inaczej mówiąc, język akceptowany przez automat składa się dokładnie z tych słów, które ten automat akceptuje.

Przykład

Automat akceptujący słowa nad alfabetem {a,b} zawierające podsłowo aa.

 

 

Przykład

Automat akceptujący $\{ x \in \{0, 1\}^* : x$ w układzie binarnym jest podzielne przez 3 }.

 

Stany reprezentują reszty modulo 3. Po wczytaniu dowolnego ciągu cyfr automat jest w stanie odpowiadającym reszcie z dzielenia wczytanej liczby przez 3. Stan początkowy (odpowiadający wczytaniu $\varepsilon$) to 0. Budując przejścia automatu musimy się zastanowić, jak zmienia się reszta z dzielenia danej liczby przez 3, gdy do jej zapisu binarnego dopiszemy (z prawej strony) 0 lub 1. Korzystamy tu z następujących tożsamości:

$$x0 = 2 \cdot x \equiv (2 \cdot (x \mod 3)) \mod 3$$

$$x1 = 2 \cdot x + 1 \equiv (2 \cdot (x \mod 3) + 1) \mod 3$$

Czyli $\delta(q,x) = (2 \cdot q + x) \mod 3$.

Własności klasy języków akceptowanych przez deterministyczne automaty skończone

Zajmiemy się teraz własnościami klasy języków akceptowanych przez deterministyczne automaty skończone. Jak się później okaże, jest to dokładnie klasa języków regularnych. Zanim się to jednak stanie, pokażemy, że automaty skończone mają niektóre z cech wzorców, które pokazaliśmy w poprzednim wykładzie.

Dowód:

Niech A będzie skończonym językiem. Wszystkie słowa z A razem wzięte mają skończoną liczbę prefiksów. Stanami automatu akceptującego A będą właśnie te prefiksy, plus jeden dodatkowy stan, który będziemy nazywać ,,śmietnikiem''. Po wczytaniu dowolnego słowa, jeżeli jest ono prefiksem pewnego słowa z A, nasz automat będzie dokładnie w takim stanie jak to słowo. Natomiast po wczytaniu słowa, które nie jest prefiksem żadnego słowa z A automat przejdzie do śmietnika.

Stan początkowy to $\varepsilon$. Jeśli q i qa są prefiksami pewnego słowa z A, to $\delta(q,a) = qa$, wpp. $\delta(q,a) =$ śmietnik. Stany akceptujące to te prefiksy, które należą do A.

W oczywisty sposób, język akceptowany przez automat to A. Natomiast dzięki temu, że słowa z A mają skończoną liczbę prefiksów, jest to poprawny automat skończony.

Przykład

Weźmy język A = {ab, aba, abb, baa }. Prefiksy słów z tego języka tworzą zbiór: $\{\varepsilon, a, b, ab, ba, aba, abb, baa\}$. W rezultacie otrzymujemy automat postaci:

 

 

Twierdzenie:

Niech A i B będą językami (nad tym samym alfabetem $\Sigma$) akceptowanymi odpowiednio przez automaty deterministyczne $M_1 = \angles{Q_1, \Sigma, \delta_1, s_1, F_1}$ i $M_2 = \angles{Q_2, \Sigma, \delta_2, s_2, F_2}$, L(M₁) = A, L(M₂) = B. Wówczas następujące języki są również akceptowane przez pewne deterministyczne automaty skończone:

• $\overline{A}$,
• $A \setint B$,
• $A \setsum B$.

Dowód:

• Dopełnienie: Weźmy $M_1' = \angles{Q_1, \Sigma, \delta_1, s_1, Q \setminus F_1}$. Mamy:
  
  $$\begin{eqnarray*} L(M_1') &=& \{x \in \Sigma^* : \delta_1^*(s_1,x) \in Q \setm... ...igma^* \setminus L(M_1) = \Sigma^* \setminus A = \overline{A} \end{eqnarray*}$$
  
  Tak więc $\overline{A}$ jest akceptowany przez M'₁.
• Weźmy $M_3 = \angles{ Q_1 \times Q_2, \Sigma, \delta_3, (s_1, s_2), F_1 \times F_2 }$, przy czym $\delta_3 ((q_1,q_2), a) = (\delta_1(q_1,a), \delta_2(q_2,a))$.

  Automat taki nazywamy automatem produktowym. Jego stany to stany automatów M₁ i M₃. Symuluje on równocześnie działanie obydwóch tych automatów. Jednocześnie akceptuje tylko takie słowa, które byłyby zaakceptowane równocześnie przez M₁ i M₂.

  Można pokazać (przez indukcję po długości słowa x), że $\delta_3^* ((p, q), x) = (\delta_1^* (p, x), \delta_2^* (q, x))$. Stąd uzyskujemy:
  

  $$\begin{eqnarray*} L(M_3) &=& \{x \in \Sigma^* : \delta_3^*((s_1,s_2), x) \in ... ...2, x) \in F_2 \} = \\ &=& L(M_1) \setint L(M_2) = A \setint B \end{eqnarray*}$$
  
  Tak więc $A \setint B$ jest akceptowany przez M₃.
• Z praw De Morgana mamy $A \setsum B = \overline{\overline{A} \setint \overline{B}}$. Stąd $A \setsum B$ jest akceptowany przez pewien deterministyczny automat skończony.

Przykład

Oto dwa automaty, pierwszy akceptujący słowa zawierające parzystą liczbę liter b i drugi akceptujący słowa zawierające nieparzystą liczbę liter a, oraz ich automat produktowy (akceptujący te słowa, które zawierają parzystą liczbę liter b i nieparzystą liczbę liter a).

 

Podsumowanie

Ten wykład był poświęcony deterministycznym automatom skończonym. Poznaliśmy ich budowę i sposób działania. Poznaliśmy też podstawowe operacje, na które domknięta jest klasa języków akceptowanych przez automaty deterministyczne. Jak się okaże w dalszej części kursu, jest to dokładnie klasa języków regularnych.

Skorowidz

• Automat skończony, deterministyczny to dowolna taka piątka $M = \angles{Q, \Sigma, \delta, s, F}$, w której: Q to skończony zbiór stanów, $\Sigma$ to (skończony) alfabet wejściowy, $\delta: Q \times \Sigma \to Q$ to funkcja przejścia, s to stan początkowy, $F \subseteq Q$ to zbiór stanów akceptujących.

• Automat produktowy to automat symulujący równocześnie działanie dwóch danych automatów deterministycznych -- jego zbiór stanów to produkt kartezjański zbiorów stanów danych automatów.

• Język akceptowany przez deterministyczny automat skończony $M = \angles{Q, \Sigma, \delta, s, F}$ to język postaci:
  
  $$L(M) \equiv \{ x \in \Sigma^* : \delta^* (s, x) \in F \}$$
  
  

• Przejście to zmiana stanu -- od stanu w chwili poprzedniej do stanu w chwili następnej. Zwykle przejście ma miejsce jako reakcja na pewne zdarzenie.

• Stan jakiegokolwiek systemu (czy mechanizmu), to pełna informacja na jego temat w danym momencie czasu. W szczególności stan zawiera wszelką ,,pamięć'' w jaką wyposażony jest dany system.

Praca domowa

1. (3p.) Podaj deterministyczny automat skończony akceptujący te słowa nad alfabetem {0, 1}, w których kazda seria zer i każda seria jedynek jest parzystej długości.

2. (3p.) Podaj deterministyczny automat skończony akceptujący te słowa nad alfabetem {a, b}, które zawierają podsłowo babbb.

3. (4p.) Podaj deterministyczny automat skończony akceptujący przecięcie języków akceptowanych przez automaty:
   
   $$\begin{array}[t]{rc\vert cc} & & a & b \\ \hline \to F ... ... b \\ \hline \to & 1 & 2 & 1\\ F & 2 & 1 & 2 \end{array}$$
   
   

Ćwiczenia

Podaj deterministyczne automaty skończone akceptujące następujące języki:

1. słowa nad alfabetem {0, 1}, które zawierają parzystą liczbę zer, Rozwiązanie
   Jedno z możliwych rozwiązań to:

   

   
   zamknij

2. słowa nad alfabetem {a, b} zakończone na aa, Rozwiązanie
   Jedno z możliwych rozwiązań to:

   

   
   zamknij

3. słowa nad alfabetem {0, 1}, w których wszystkie 1-ki znajdują się na parzystych pozycjach, Rozwiązanie
   Jedno z możliwych rozwiązań to:

   

   
   zamknij

4. Podaj deterministyczny automat skończony akceptujący te słowa nad alfabetem {0, 1}, w których między każdymi dwoma kolejnymi jedynkami jest parzysta liczba zer. Rozwiązanie
   Jedno z możliwych rozwiązań to:

   

   
   zamknij

5. słowa nad alfabetem {0, 1}, w których na wszystkich parzystych pozycjach występują 1-ki, Rozwiązanie
   Jedno z możliwych rozwiązań to:

   

   
   zamknij

6. słowa nad alfabetem {1, 2, 3, 4} zawierające podsłowo 42,
7. słowa nad alfabetem {a} o długości podzielnej przez 2 lub 3,
8. słowa nad alfabetem {a, b} zawierające podsłowo abb,
9. słowa nad alfabetem {a, b} nie zawierające podsłowa aba,
10. słowa nad alfabetem {a, b} zawierające podsłowo abba, Rozwiązanie
    

    
    zamknij

11. słowa nad alfabetem {a, b} zawierające podsłowo ababb, Rozwiązanie
    

    
    zamknij

12. słowa nad alfabetem {a, b} zawierające przynajmniej 2 wystąpienia słowa aba (być może zachodzące na siebie),
13. te słowa nad alfabetem {a, b}, w których pierwszy i ostatni znak są takie same (uwaga, słowa a i b powinny zostać zaakceptowane),
14. te słowa nad alfabetem $\{0, 1, \dots, 9\}$, które zawierają jako podsłowo wybrany przez Ciebie numer telefonu,
15. zapisy 10-tne liczb podzielnych przez 3,
16. te słowa nad alfabetem {0,1}, w których każde dwa kolejne znaki, licząc od początku słowa, zawierają choć jedną 1-kę,
17. przecięcie/sumę języków akceptowanych przez automaty:
    
    $$\begin{array}[t]{rc\vert cc} & & a & b \\ \hline \to & ... ... b \\ \hline \to & 1 & 1 & 2\\ F & 2 & 1 & 2 \end{array}$$
    
    
    Rozwiązanie
    Oto automat produktowy akceptujący przecięcie tych języków:
    

    $$\begin{array}[b]{rc\vert cc} & & a & b \hline \to & (1... ...\end{array} \hspace{0.2\textwidth} \includegraphics{rys-4-j}$$

    
    

    
    zamknij

18. przecięcie/sumę języków akceptowanych przez automaty:
    
    $$\begin{array}[t]{rc\vert cc} & & a & b \\ \hline \to F ... ... b \\ \hline \to & 1 & 2 & 1\\ F & 2 & 1 & 1 \end{array}$$
    
    
    Rozwiązanie
    Oto automat produktowy akceptujący przecięcie tych języków:
    

    $$\begin{array}[b]{rc\vert cc} & & a & b \hline \to & (1... ...\end{array} \hspace{0.2\textwidth} \includegraphics{rys-4-m}$$

    
    

    
    zamknij

19. przecięcie/sumę języków akceptowanych przez automaty:
    
    $$\begin{array}[t]{rc\vert cc} & & a & b \\ \hline \to F ... ... b \\ \hline \to & 1 & 1 & 2\\ F & 2 & 2 & 1 \end{array}$$
    
    

20. przecięcie/sumę języków akceptowanych przez automaty:
    
    $$\begin{array}[t]{rc\vert cc} & & a & b \\ \hline \to & ... ... b \\ \hline \to F & 1 & 2 & 1\\ & 2 & 1 & 2 \end{array}$$
    
    

21. przecięcie/sumę języków akceptowanych przez automaty:
    
    $$\begin{array}[t]{rc\vert cc} & & a & b\\ \hline \to & 1... ...to F & 1 & 2 & 3\\ & 2 & 3 & 1 \\ & 3 & 1 & 2 \end{array}$$