Języki, automaty i obliczenia/Wykład 6: Automat niedeterministyczny. Lemat o pompowaniu

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

W tym wykładzie zdefiniujemy automat niedeterministyczny, udowodnimy jego równoważność z automatem deterministycznym oraz podamy algorytm konstrukcji równoważnego automatu deterministycznego. Wprowadzimy także automaty niedeterministyczne z pustymi przejściami. W ostatniej części wykładu sformułujemy lemat o pompowaniu dla języków rozpoznawanych przez automaty skończenie stanowe.

Automat niedeterministyczny

Wprowadzony wcześniej automat jest modelem obliczeń, czy też mówiąc ogólniej, modelem procesu o bardzo prostym opisie. Stan procesu zmienia się w sposób jednoznaczny pod wpływem sygnału zewnętrznego reprezentowanego przez literę alfabetu. Opisem tych zmian jest więc funkcja. Pewnym uogólnieniem powyższej sytuacji może być dopuszczenie relacji, która opisuje zmiany stanu. W efekcie opis zmiany stanów staje się niedeterministyczny w tym sensie, że z danego stanu automat przechodzi w pewien zbiór stanów. Jak udowodnimy pó{z}niej, z punktu widzenia rozpoznawania lub poprawnych obliczeń, takie uogólnienie nie rozszerza klasy języków rozpoznawanych przez automaty.

Definicja 1.1.

Automatem niedeterministycznym nad alfabetem nazywamy system w którym jest dowolnym zbiorem, zwanym zbiorem stanów, a funkcją przejść.

Funkcję przejść rozszerzamy do funkcji określonej na całym wolnym monoidzie w następujący sposób:

dla każdego

dla każdego oraz dowolnego

Zwróćmy uwagę, że prawa strona ostatniej równości to obraz przez funkcję zbioru i litery . Funkcję przejść automatu niedeterministycznego można także traktować jako relację

W związku z powyższą definicją automat wprowadzony wcześniej, w wykładzie 3, będziemy nazywać automatem deterministycznym.

Definicja 1.2.

Język jest rozpoznawalny przez automat niedeterministyczny wtedy i tylko wtedy, gdy istnieje -- zbiór stanów początkowych oraz - zbiór stanów końcowych taki, że

Niedeterministyczny automat rozpoznający język będziemy oznaczać jako system lub jeśli wiadomo, nad jakim alfabetem określono automat.

Na pierwszy rzut oka mogłoby się wydawać, że wprowadzony automat istotnie rozszerza możliwości automatu deterministycznego, że jego moc obliczeniowa jest istotnie większa. Okazuje się jednak, że z punktu widzenia rozpoznawania języków, czyli właśnie z punktu widzenia mocy obliczeniowej, automaty deterministyczne i niedeterministyczne są równoważne.

Twierdzenie 1.1.

Język jest rozpoznawany przez automat deterministyczny wtedy i tylko wtedy, gdy jest rozpoznawany przez automat niedeterministyczny.

Dowód

Rozpocznijmy dowód od oczywistej obserwacji. Zauważmy, iż każdy automat deterministyczny można przekształcić w niedeterministyczny, modyfikując funkcję przejść w ten sposób, że jej wartościami są zbiory jednoelementowe. Modyfikacja ta prowadzi w konsekwencji do równoważnego automatu niedeterministycznego.

Dla dowodu implikacji w stronę przeciwną załóżmy, że język , gdzie , jest automatem niedeterministycznym. Określamy teraz równoważny, jak się okaże, automat deterministyczny. Jako zbiór stanów przyjmujemy , czyli ogół podzbiorów zbioru . Funkcję przejść określamy kładąc dla

dowolnego stanu oraz dowolnej litery

a następnie rozszerzamy ją do . Łatwo sprawdzić, że funkcja spełnia warunki funkcji przejść. Przyjmując następnie zbiór jako stan początkowy oraz zbiór , jako zbiór stanów końcowych stwierdzamy, dla określonego automatu , równość

Skonstruowany automat jest zatem deterministyczny i równoważny wyjściowemu, co kończy dowód twierdzenia.

End of proof.gif
Uwaga 1.1.

Dla określonego w dowodzie automatu na ogół nie wszystkie stany są osiągalne ze stanu . Aby uniknąć takich stanów, które są bezużyteczne, funkcję przejść należy zacząć definiować od stanu i kolejno określać wartości dla już osiągniętych stanów.

Przykład 1.1.

Automat nad alfabetem określony przez zbiory i

zadany poniższym grafem jest przykładem automatu niedeterministycznego.
Rysunek 1

Automat ten, jak łatwo teraz zauważyć, rozpoznaje język .

Przedstawimy teraz algorytm, który mając na wejściu automat niedeterministyczny konstruuje równoważny automat deterministyczny.

Algorytm Determinizacja - buduje deterministyczny automat równoważny automatowi niedeterministycznemu



  1  Wejście:  - automat niedeterministyczny.
  2  Wyjście:  - automat deterministyczny taki,
że . 3 ; 4 ; 5 ; jest kolejką 6 while do 7 zdejmij ; 8 if then ; 9 for each do 10 ; 11 if then 12 ; 13 włóż ; 14 end if 15 ; 16 end for 17 end while 18 return ;


Funkcja zdejmij, występująca w linii 7., zdejmuje z kolejki element znajdujący się na jej początku i zwraca go jako swoją wartość. Procedura włóż z linii 13. wstawia na koniec kolejki element .

Należy zauważyć, że algorytm determinizujący automat jest algorytmem eksponencjalnym. Stany wyjściowego automatu deterministycznego etykietowane są podzbiorami zbioru stanów . Jeśli pewien stan etykietowany jest zbiorem zawierającym stan końcowy z , to staje się stanem końcowym w automacie .

Z analizy algorytmu Determinacja wynika, że w ogólności zbiór stanów wyjściowego automatu deterministycznego może osiągać wartość rzędu , gdzie jest ilością stanów automatu niedeterministycznego.

Zastosujemy powyższy algorytm do uzyskania automatu deterministycznego równoważnego automatowi z przykładu 1.1. (patrz przykład 1.1.) Kolejne etapy działania ilustruje zamieszczona tu animacja 1.

Automaty niedeterministyczne z przejściami pustymi

Rozszerzenie definicji automatu skończenie stanowego do automatu niedeterministycznego nie spowodowało, jak wiemy, zwiększenia mocy obliczeniowej takich modeli. Nasuwać się może pytanie, czy dołączenie do tego ostatniego modelu możliwości wewnętrznej zmiany stanu, zmiany stanu bez ingerencji sygnału zewnetrznego, czyli bez czytania litery nie zwiększy rodziny jezyków rozpoznawanych.

Model taki, zwany automatem z pustymi przejściami (w skrócie: automat z p-przejściami), zdefiniujemy poniżej.

Definicja 2.1.

Automatem niedeterministycznym z pustymi przejściami nad alfabetem nazywamy system w którym jest dowolnym zbiorem, zwanym zbiorem stanów, a funkcją przejść.

Uwaga 2.1.

Słowo puste występuje w powyższej definicji w dwóch rolach. Pierwsza, to znana nam rola elementu neutralnego katenacji słów. Druga, to rola jakby "dodatkowej" litery, która może powodować zmianę aktualnego stanu automatu na inny. Ponieważ słowo puste może wystąpić przed i po każdej literze dowolnego słowa (i to wielokrotnie), dlatego też czytając słowo , automat zmienia stany zgodnie nie tylko z sekwencją liter tego słowa, ale także z uwzględnieniem tej drugiej roli słowa pustego.

Rozszerzając powyższą definicję poprzez dodanie zbioru stanów początkowych i zbioru stanów końcowych, uzyskamy niedeterministyczny automat z pustymi przejściami dla którego będziemy mogli zdefiniować język rozpoznawany. W tym celu określimy najpierw działanie takiego automatu pod wpływem dowolnego słowa . Jeśli oraz , to

Zwróćmy uwagę, iż zbiór określający wartość rozszerzonej funkcji jest skończony i efektywnie obliczalny, bo zbiór stanów automatu jest skończony. Jeśli teraz oraz , to

Stany ze zbioru będziemy nazywać stanami osiągalnymi z pod wpływem słowa . Prawdziwe jest następujące twierdzenie, które orzeka, iż z punktu widzenia rozpoznawania automaty niedeterministyczne z pustymi przejściami rozpoznają dokładnie te same języki, co automaty niedeterministyczne.

Twierdzenie 2.1.

Język jest rozpoznawany przez automat niedeterministyczny z pustymi przejściami wtedy i tylko wtedy, gdy jest rozpoznawany przez automat niedeterministyczny.

Dowód

(szkic) Fakt, że język rozpoznawany przez automat niedeterministyczny jest rozpoznawany przez automat niedeterministyczny z pustymi przejściami jest oczywisty.

Dowód implikacji w drugą stronę polega na takiej modyfikacji automatu niedeterministycznego z pustymi przejściami rozpoznającego jezyk , by uzyskać automat bez pustych przejść i nie ograniczyć ani nie zwiększyć jego możliwości rozpoznawania. Zarysujemy ideę tej konstrukcji. Niech będzie automatem niedeterministycznym z pustymi przejściami akceptującym język . W konstruowanym automacie pozostawiamy zbiór stanów i zbiór stanów początkowych bez zmian. Jeśli z któregoś ze stanów początkowych z jest możliwość osiągnięcia jakiegoś stanu końcowego z , to dodajemy stan początkowy do zbioru stanów końcowych, czyli zbiór stanów końcowych w konstruowanym automacie ma postać . Jeśli nie ma takiej możliwości, to zbiór stanów końcowych pozostaje niezmieniony. Określamy wartość funkcji przejść dla dowolnego stanu i litery jako zbiór wszystkich stanów osiągalnych ze stanu pod wpływem . Tak skonstruowany automat niedeterministyczny nie ma pustych przejść i jak można wykazać, indukcyjnie ze względu na długość słowa, rozpoznaje dokładnie język .

End of proof.gif

Algorytm usuwania przejść pustych i prowadzący do równoważnego automatu niedeterministycznego przedstawiony jest w ćwiczeniach do tego wykładu.

Lemat o pompowaniu

Jedną z wielu własności języków rozpoznawanych przez automaty skończone, i chyba jedną z najważniejszych, przedstawia prezentowane poniżej twierdzenie, zwane tradycyjnie w literaturze lematem o pompowaniu. Istota własności "pompowania" polega na tym, iż automat, mając skończoną ilość stanów, czytając i rozpoznając słowa dostatecznie długie, wykorzystuje w swoim działaniu pętlę, czyli powraca do stanu, w którym znajdował się wcześniej. Przez taką pętlę automat może przechodzić wielokrotnie, a co za tym idzie, "pompować" rozpoznawane słowo, wprowadzając do niego wielokrotnie powtarzane podsłowo odpowiadające tej pętli.

Twierdzenie 3.1. (Lemat o pompowaniu)

Niech będzie językiem rozpoznawalnym. Istnieje liczba naturalna taka, że dowolne słowo o długości można rozłożyć na katenację gdzie , oraz

Dowód

Niech , gdzie jest deterministycznym automatem skończenie stanowym. Niech i rozważmy dowolne słowo takie, że . Oznaczmy:

Słowo jest akceptowane przez automat , więc Ponieważ oraz , to istnieją , takie, że .

Przyjmując teraz dochodzimy do nastepującej konkluzji:


A to oznacza, że słowo jest rozpoznawane przez automat dla dowolnej liczby , co kończy dowód. Nierówność wynika w oczywisty sposób z przyjętego na początku dowodu założenia, że .

End of proof.gif

Istotę dowodu przedstawia następująca animacja 2.


Wniosek 3.1.

Jeśli rozpoznawalny język jest nieskończony, to istnieją słowa takie, że

Wniosek 3.2.

Jeśli rozpoznawalny język nie jest zbiorem pustym, to istnieje słowo takie, że , gdzie jest stałą występującą w lemacie o pompowaniu.
Jeśli słowo i , to zgodnie z lematem o pompowaniu możemy przedstawić słowo jako , gdzie oraz dla . Przyjmując , mamy i . Powtarzając powyższy rozkład skończoną ilość razy, otrzymamy słowo należące do języka , o długości mniejszej od .

Lemat o pompowaniu wykorzystuje się najczęściej do uzasadnienia faktu, iż pewne języki nie są rozpoznawane przez automaty skończone. Przyjrzyjmy się bliżej technice takiego uzasadnienia.

Przykład 3.1.

Rozważmy język nad alfabetem . W oparciu o lemat o pompowaniu wykażemy, że język nie jest rozpoznawany. Dla dowodu nie wprost, przypuszczamy, że jest rozpoznawany. Na podstawie udowodnionego lematu istnieją zatem słowa takie, że oraz Biorąc pod uwagę formę słów języka , wnioskujemy, że

  • słowo nie może składać się tylko z liter , gdyż słowo zawierałoby więcej liter niż ,
  • słowo nie może składać się tylko z liter , gdyż słowo zawierałoby więcej liter niż ,
  • słowo nie może składać się z liter , gdyż w słowie litera poprzedzałaby literę .

Ponieważ słowo należy do języka , więc każdy z wyprowadzonych powyżej wniosków prowadzi do sprzeczności.