Języki, automaty i obliczenia/Wykład 8: Dalsze algorytmy dla języków regularnych. Problemy rozstrzygalne

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

W tym wykładzie przedstawimy algorytmy konstrukcji gramatyki regularnej, automatu skończenie stanowego oraz wyrażeń regularnych opisujących ten sam język . Omówimy także problemy rozstrzygalne algorytmicznie w klasie języków regularnych.

Dalsze algorytmy języków regularnych

Dowód twierdzenia z ostatniego wykładu, w którym udowodniliśmy równoważność rozpoznawania języka i generowania tego języka przez gramatykę regularną daje podstawę do określenia dwóch algorytmów. Algorytmu konstruującego automat skończony w oparciu o daną gramatykę regularną i oczywiście akceptujący język generowany przez tę gramatykę oraz algorytmu budowy gramatyki regularnej dla zadanego automatu. Bez utraty ogólności przyjmujemy, że automat jest deterministyczny.

Idea działania algorytmu Automat2GReg jest następująca: każdy symbol nieterminalny tworzonej gramatyki odpowiada pewnemu stanowi automatu. Jeśli w automacie pod wpływem litery następuje przejście ze stanu do stanu , to do zbioru praw gramatyki dodawane jest prawo . Ponadto, jeśli stan jest stanem końcowym, to dodajemy także prawo , aby w danym miejscu wywód słowa mógł zostać zakończony.

Algorytm Automat2GReg - buduje gramatykę regularną dla zadanego automatu skończonego.



  1  Wejście:  - automat niedeterministyczny.
  2  Wyjście:  - gramatyka regularna taka, że .
  3  ;
  4  ;
  5  ;
  6  ;
  7  for each   do
  8    for each   do
  9      if NULL then
 10        ;                  funkcja  jest określona na 
 11        ;
 12        if  then
 13          ;
 14        end if
 15      end if
 16    end for
 17  end for
 18  return ;

Oznaczmy przez ilość krawędzi w grafie -stanowego automatu niedeterministycznego . Złożoność czasowa liczona względem jest liniowa i równa . Również złożoność pamięciowa jest liniowa i wynosi .

Przykład 1.1

Niech dany będzie automat pokazany na rysunku 1. Zbudujemy gramatykę, która będzie

generowała język akceptowany przez .
Rysunek 1

Ponieważ , a ponadto jest stanem końcowym, do dodajemy produkcje oraz . Dodajemy także produkcję , gdyż mamy .

Fakt, że oraz sprawia, że do dodajemy: , .

Ponieważ do dodajemy: oraz , gdyż .

Symbolem początkowym nowej gramatyki jest symbol . Ostatecznie gramatyka ma postać:

Zwróćmy uwagę na wygodny zapis produkcji gramatyki, jaki został użyty powyżej. Produkcje o tej samej lewej stronie (wspólnym symbolu nieterminalnym) zapisywane są razem, a prawe strony tych produkcji oddzielane są pionowymi kreskami.

Przedstawiony poniżej algorytm GReg2Automat konstruuje automat skończenie stanowy, akceptujący język generowany przez zadaną gramatykę.

Zauważmy, że gramatyka podana na wejściu algorytmu nie może zawierać produkcji postaci , gdzie , . Jeśli gramatyka zawiera takie produkcje, to możemy się ich łatwo pozbyć, zgodnie z Twierdzeniem 2.2 z Wykładu 7 (patrz twierdzenie 2.2 wykład 7), uzyskując oczywiście gramatykę równoważną.

Idea działania algorytmu jest podobna do poprzedniej - każdy tworzony stan automatu odpowiadać będzie pewnemu symbolowi nieterminalnemu gramatyki wejściowej. Zależnie od postaci produkcji gramatyki, niektóre stany będą stanami końcowymi.

Zapis w linii 7. symbolicznie oznacza, że funkcja przejść nie jest jeszcze określona.

W pętli 8.-15. pozbywamy się produkcji, w których występuje więcej niż jeden terminal; każdą taką produkcję "rozbijamy" na sekwencję produkcji postaci , gdzie .

Algorytm GReg2Automat - buduje automat dla zadanej gramatyki regularnej.



  1  Wejście:  - gramatyka regularna.
  2  Wyjście:  - automat taki, że .
  3  ;
  4  ;
  5  ;                                    nie ma jeszcze stanów końcowych
  6  ;
  7  ;                  funkcja  nie jest określona dla żadnego argumentu
  8  for each   do
  9    if  then
 10      ;      rozbijamy produkcję na kilka prostszych
 11      ;            w tym celu usuwamy produkcję z 
 12      ;     w zamian dodając ciąg krótszych
 13      ;
 14    end if
 15  end for
 16     wszystkie produkcje są postaci  lub , gdzie , 
 17  for each  do
 18    ;
 19  end for
 20  for each   do
 21    ;
 22  end for
 23  return ;

Przykład 1.2

Jako wejście algorytmu rozważmy gramatykę z przykładu 1.1 (patrz przykład 1.1.) Używając algorytmu Greg2Automat, zbudujemy dla niej automat akceptujący język przez nią generowany.

Mamy . W liniach 17. -- 19. określana jest funkcja przejścia: , , , oraz .

Pętla w liniach 20. - 22. przebiega po dwóch produkcjach: oraz , dodaje zatem do zbioru stanów końcowych stany oraz . Szukany automat to automat z poprzedniego przykładu; przedstawiony jest na rysunku 1.

Automat powstały w wyniku działania algorytmu GReg2Automat nie musi być automatem deterministycznym (wystarczy, że w zbiorze produkcji znajdą się dwie produkcje postaci oraz dla pewnego ), jednak po jego determinizacji i minimalizacji otrzymujemy minimalny automat deterministyczny akceptujący język, który jest generowany przez gramatyke podaną na wejście algorytmu.

Złożoność czasowa jak i pamięciowa algorytmu wynosi , gdzie jest liczbą produkcji występujących w zbiorze praw gramatyki.

Przedstawimy teraz algorytmy związane z wyrażeniami regularnymi. Pierwszy z nich prowadzi do konstrukcji automatu skończenie stanowego, rozpoznającego język opisany wyrażeniem regularnym. Drugi, mając na wejściu automat, konstruuje wyrażenie regularne opisujące język rozpoznawany przez ten automat.

Rozpoczynamy od algorytmu prowadzącego do konstrukcji automatu na podstawie wyrażenia regularnego.

Niech . Najpierw pokażemy, że językom odpowiadającym wyrażeniom regularnym , , , , oraz można przyporządkować automaty akceptujące te języki, a następnie podamy algorytm konstruowania automatu rozpoznającego dowolne wyrażenie regularne.

Na rysunku 2 przedstawione są trzy automaty. Automat a) rozpoznaje język pusty, automat b) - język , a automat c) - język , dla .

Rysunek 2

Niech dane będą automaty: , akceptujący język opisywany wyrażeniem oraz , akceptujący język opisywany wyrażeniem . Na rysunku 3 przedstawiono konstrukcje automatów akceptujących wyrażenia regularne (automat a)), (automat b)) oraz (automat c)).

Rysunek 3

W automacie a) stan jest stanem początkowym, stan - stanem końcowym, stany oraz oznaczają odpowiednio stany początkowe automatów i oraz stany końcowe automatów i .

W automacie b) stan jest jednocześnie jego stanem początkowym oraz stanem początkowym automatu , stan jest stanem końcowym automatu b) i jednocześnie stanem końcowym automatu . Stan jest stanem końcowym w , a - początkowym w .

W automacie c) stan jest jego stanem początkowym a końcowym. Stany oraz to odpowiednio początkowy i końcowy stan automatu .

Wyrażenia regularne można przedstawiać w postaci drzewa, w którym liśćmi są litery, słowo puste 1 lub zbiór pusty , a węzły symbolizują operacje na wyrażeniach regularnych, czyli sumę, konkatenację lub iterację, czyli gwiazdkę Kleene'ego.

Przykład 1.3

Rozważmy wyrażenie regularne . Drzewo odpowiadające przedstawione jest na rysunku 4. Korzeniem jest wierzchołek z małą wchodzącą strzałką.

Rysunek 4

Powyższe konstrukcje będą stosowane podczas iteracyjnej budowy automatu. Algorytm do tego celu będzie wykorzystywał drzewo odpowiadające wyrażeniu regularnemu w następujący sposób: drzewo będzie przeszukiwane metodą post-order (zaczynając od korzenia), tzn. najpierw rekurencyjnie przeszukiwane są poddrzewa danego węzła , a na końcu sam węzeł . Dzięki temu, wchodząc do węzła drzewa etykietowanego daną operacją na wyrażeniu regularnym oba poddrzewa i wierzchołka będą już reprezentowane przez automaty oraz . Teraz wystarczy zastosować jedną z konstrukcji z rysunku 2 lub 3. Procedurę powtarzamy do momentu, aż przechodzenie drzewa zakończy się w korzeniu. Szukanym przez nas automatem będzie automat "odpowiadający" korzeniowi drzewa.

Poniżej przedstawiony jest algorytm konstrukcji automatu w oparciu o wyrażenie regularne. Jego istotną część składową stanowi procedura PostOrder, której pseudo-kod jest przedstawiony poniżej. Wykorzystamy także dwie procedury, mianowicie CreateAutomata(type) oraz JoinAutomata(type,). Zmienna type może przyjmować wartości '', '' lub ''. Funkcja zwraca automat CreateAutomata(type) przedstawiony (zależnie od zmiennej type) na rysunku 2. Procedura JoinAutomata(type,) natomiast konstruuje na podstawie automatów , automat z rysunku 2, przy czym dla przypadku type= automat jest bez znaczenia. Ostatnią wykorzystaną procedurą będzie BuildTree(r), tworząca drzewo (binarne) dla wyrażenia regularnego. Zakładamy, że studentowi doskonale jest znana Odwrotna Notacja Polska i budowa takiego drzewa nie będzie dla niego stanowiła problemu. Dla ustalenia uwagi zakładamy, że symbol prowadzi zawsze do lewego dziecka.

Poniżej przedstawiamy oznaczenia standardowych funkcji operujących na drzewach. Funkcja zwraca korzeń drzewa , funkcje oraz zwracają lewe i prawe dziecko wierzchołka (ew. NULL, gdy brak lewego lub prawego dziecka), natomiast funkcja zwraca etykietę wierzchołka drzewa . Funkcja zwraca wartość , gdy jest liściem w drzewie oraz w przypadku przeciwnym.

Algorytm Wr2Automat -- buduje automat rozpoznający język opisywany wyrażeniem regularnym



  1  Wejście:  -- wyrażenie regularne.
  2  Wyjście:  -- automat rozpoznający język opisywany wyrażeniem .
  3  ;
  4  ;
  5   PostOrder();
  6  return ;

Przykład 1.4

Zastosujemy algorytm Wr2Automat do konstrukcji automatu dla wyrażenia regularnego .

Automat jest zwrócony przez algorytm jako automat akceptujący język opisywany wyrażeniem . Automat ten przedstawiony jest na rysunku 5.

Rysunek 5

Ramkami zaznaczono i opisano automaty budowane w trakcie działania procedury PostOrder.

Rezultat działania algorytmu Wr2Automat może nie być zadawalający, gdyż wynikiem działania algorytmu nie jest automat deterministyczny, lecz automat z pustymi przejściami. Automat ten można więc poddać procesowi usunięcia przejść pustych oraz determinizacji, co można przeprowadzić przy pomocy omówionych wcześniej algorytmów UsuńPustePrzejścia oraz Determinizuj.

Algorytm Procedure PostOrder



  1  procedure PostOrder (: drzewo, : wierzchołek)
  2  if IsLeaf() then
  3    if =NULL then
  4       CreateAutomata('');
  5    else
  6      if Label()='1' then
  7         CreateAutomata('');
  8      else
  9         CreateAutomata('');  Label
 10      end if
 11    end if
 12    return ;
 13  else
 14     PostOrder(,  LeftChild);
 15     PostOrder(, RightChild);
 16    if Label()='' then 
 17      JoinAutomata('');
 18    end if
 19    if Label()='' then
 20      JoinAutomata('');
 21    end if
 22    if Label()='' then
 23      JoinAutomata('');
 24    end if
 25    return ;
 26  end if
 27  end procedure

Procedura tworzenia drzewa dla wyrażenia regularnego działa w czasie liniowym ze względu na długość napisu reprezentującego wyrażenie regularne -- napis ten można najpierw przekształcić do równoważnego mu, zapisanego w Odwrotnej Notacji Polskiej, a następnie, przechodząc od lewej strony do prawej, konstruować po kolei fragmenty drzewa.

Przechodzimy teraz do algorytmów konstruujących wyrażenie regularne na podstawie zadanego automatu. Pierwszą metodę, można powiedzieć klasyczną i omawianą w większości podręczników, prezentujemy poniżej. Drugą, nieco prostszą i wygodniejszą w zastosowaniu, przedstawimy w ćwiczeniach do tego wykładu.

Niech dany będzie automat . Zbudujemy wyrażenie regularne opisujące język akceptowany przez .

Konstrukcja polega na obliczeniu zbiorów (definicja poniżej), gdzie , co jest równoważne konstrukcji pewnych wyrażeń regularnych . Szukany język będzie odpowiadał sumie pewnych zbiorów , a zatem opisywany będzie przez wyrażenie regularne postaci dla pewnych , oraz .

Załóżmy, że zbiór stanów automatu jest postaci . Wprowadźmy porządek na

zbiorze , przyjmując:

Zbiory definiujemy w następujący sposób:

Intuicyjnie, zbiór to ogół wszystkich słów takich, że , a ponadto jeśli , to .

Zamiast obliczać zbiory wygodniej będzie od razu zapisywać odpowiadające im wyrażenia regularne, które oznaczać będziemy poprzez . Przez analogię mamy wzór rekurencyjny:

Pozostaje wyjaśnić jak wyglądają wyrażenia . Jeśli to

Twierdzenie 1.1

Niech oraz będą zdefiniowane jak powyżej i niech zbiór stanów końcowych dla ma postać . Wtedy

Powyższą metodę ujmiemy formalnie w ramy algorytmu (algorytm Automat2WR1).

Algorytm Automat2WR1 -- buduje wyrażenie regularne opisujące język akceptowany przez automat skończony.



  1  Wejście: .
  2  Wyjście:  - wyrażenie regularne opisujące język .
  3  for  to  do
  4    for  to  do
  5      oblicz                              stosujemy wzór (3);
  6    end for
  7  end for
  8  for  to  do
  9    for  to  do
 10      for  to  do
 11        ;  dokonujemy katenacji słów
 12      end for
 13    end for
 14  end for
 15   "";                            podstaw pod  słowo puste
 16  for  to   
 17    if  
 18      if r="" 
 19        ;                      stosujemy Twierdzenie 1.1
 20      else
 21        ;
 22      end if
 23    end if
 24  end for
 25  return ;

Podczas obliczania wyrażeń należy je w miarę możliwości upraszczać, gdyż, szczególnie przy dużej liczbie stanów, nieskracane, mogą rozrastać się do bardzo dużych rozmiarów.

Przykład 1.5

Znajdziemy wyrażenie regularne opisujące język akceptowany przez automat z rysunku 6.

Rysunek 6

Mamy , , , . Szukamy zatem wyrażenia regularnego .

Najpierw musimy obliczyć dla wszystich . Mamy na przykład , gdyż z definicji zachodzi: .

Gdy mamy wyliczone wszystkie , przystępujemy do obliczeń dla .

Na przykład:

co po zredukowaniu daje

Obliczone wyrażenia dla oraz dla wszystkich przedstawione są w tabeli 1.

Tabela 1. Obliczone wartości dla automatu z rys. 6

Ponieważ , szukanym wyrażeniem regularnym będzie . Obliczamy zatem:

Problemy rozstrzygalne algorytmicznie

Kończąc część wykładu prezentującą języki regularne, wskażemy problemy rozstrzygalne algorytmicznie w zakresie tej rodziny języków formalnych. Ponieważ pojęcia rozstrzygalności i nierozstrzygalności możemy uznać za znane (były wprowadzone na innych wykładach) nie będziemy tutaj ich definiować ani kreślić tła teorii rozstrzygalności.

W obrębie rodziny języków regularnych wszystkie podstawowe problemy są algorytmicznie rozstrzygalne. Uzasadnienia są proste. Część z nich opiera się na lemacie o pompowaniu, a część wynika bezpośrednio z algorytmicznej struktury automatu skończenie stanowego, czy też gramatyki regularnej.

Twierdzenie 2.1

W klasie języków regularnych następujące problemy są rozstrzygalne:

  1. problem niepustości języka,
  2. problem nieskończoności języka,
  3. problem równości języków,
  4. problem należenia słowa do języka,

Dowód

1. Aby uzasadnić ten fakt zauważmy, że wystarczy sprawdzić niepustość skończonego podzbioru języka co wynika z równoważności:

gdzie stała z lematu o pompowaniu. Implikacji jest oczywista. Natomiast fakt, że do niepustego języka należy słowo o długości ograniczonej przez , wynika z lematu o pompowaniu. Jeśli mianowicie i , to rozkładamy słowo następująco:

Przyjmując teraz wartość , uzyskujemy:

Po skończonej ilości powtórzeń powyższego rozkładu uzyskamy słowo należące do języka, o długości ograniczonej przez .

2. Wystarczy udowodnić nastepującą równoważność:

Jeśli jest językiem nieskończonym, to znajdziemy w słowo dowolnie długie. Niech . Jeśli słowo nie spełnia ograniczenia , to podobnie jak poprzednio korzystamy z lematu o pompowaniu i po skończonej ilości kroków otrzymamy słowo krótsze od . Istotne jest, że wykorzystując lemat o pompowaniu, możemy założyć, że usuwane słowo ma długość ograniczoną przez . Zatem oznacza to, że ze słowa dłuższego od nie dostaniemy słowa krótszego od .

Jeśli teraz do języka należy słowo o długości większej lub równej , to znów z lematu o pompowaniu wnioskujemy, że

Istnieje więc nieskończony podzbiór języka , a więc i sam język jest nieskończony.

3. Rozważmy . Język jest regularny, co wynika z domkniętości klasy na operaje boolowskie. Równoważność

sprowadza problem równości języków do problemu niepustości omówionego powyżej.

4. Konstruujemy automat rozpoznający język i sprawdzamy, czy

End of proof.gif

Na podstawie dowodu powyższego twierdzenia nietrudno jest określić algorytmy rozstrzygające przedstawione problemy. Poniżej prezentujemy algorytm rozstrzygający problem należenia słowa do języka regularnego zadanego automatem. Bez straty ogólności możemy założyć, że automat jest deterministyczny.

Algorytm NależenieDoJęzyka -- sprawdza, czy dane słowo należy do języka akceptowanego przez zadany automat



  1  Wejście:  - automat akceptujący język  oraz  - słowo.
  2  Wyjście: Odpowiedź true (tak) lub false (nie).
  3  ;
  4  ;
  5  for  to  do
  6    ;
  7  end for
  8  if   then
  9    return true;
 10  else
 11    return false;
 12  end if

Algorytm działa w czasie i posiada złożoność pamięciową , co spowodowane jest koniecznością przechowywania funkcji przejść automatu .

Jeśli język zadany jest nie automatem, a gramatyką regularną, to gramatykę można przekształcić na automat poznanym na początku wykładu algorytmem GReg2Automat, następnie zdeterminizować ten automat i podać go jako wejście dla algorytmu NależenieDoJęzyka.

Jeśli język zadany jest wyrażeniem regularnym, to mając wyrażenie regularne, można zbudować odpowiadający mu automat przy pomocy algorytmu WR2Automat. A zatem, na przykład, z powyższego twierdzenia wynika, iż problem równoważności wyrażeń regularnych jest rozstrzygalny.