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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ćwiczenie 1

Zastosuj algorytm Automat2GReg do automatu o następującej funkcji przejść:

gdzie jest stanem początkowym oraz .

Rozwiązanie

Ćwiczenie 2

Zbuduj automaty akceptujące języki generowane następującymi gramatykami ( oznaczają symbole nieterminalne, -- terminalne):

1. , , , , , , .

2. , , , , .

Rozwiązanie punktu 1
Rozwiązanie punktu 2

W wykładzie podany został algorytm Automat2WR1 budujący wyrażenie regularne na podstawie zadanego automatu. Opiszemy teraz inną metodę rozwiązania tego problemu, wykorzystującą równania na językach.

Dany niech będzie automat . Chcemy zbudować wyrażenie regularne opisujące język akceptowany przez . Do wyprowadzenia metody potrzebować będziemy lematu Ardena.

Lemat 0.1. [Arden]

Niech i będą językami regularnymi. Wtedy równanie

posiada jedyne rozwiązanie , które jest językiem regularnym.

Zdefiniujmy najpierw jako język tych słów, które byłyby

akceptowane przez , gdyby stanem końcowym był stan , tzn. gdyby :

Zauważmy, że jeśli do stanu wchodzą strzałki prowadzące ze stanów odpowiednio z etykietami (i tylko takie), to

Obserwacja ta jest podstawą do konstrukcji metody otrzymywania wyrażenia regularnego na podstawie automatu. Będziemy budować układ równań, w którym każde równanie będzie postaci , , gdzie traktowane są jak niewiadome. Następnie układ taki rozwiążemy ze względu na każdą zmienną (tu pomocny będzie lemat Ardena). Szukanym przez nas wyrażeniem regularnym będzie wyrażenie postaci , gdzie jest zbiorem indeksów stanów końcowych automatu .

Można postawić w tym momencie pytanie, czy budowany układ równań ma rozwiązanie, a jeśli tak, to czy jest ono jedyne. Okazuje się że w rozważanej przez nas sytuacji ma to miejsce, choć dowód tego faktu nie jest natychmiastowy. Fakt ten, podobnie jak lemat Ardena, podajemy tutaj bez dowodu.

Algorytm Automat2WR2 - buduje inną metodą wyrażenie regularne opisujące język akceptowany przez automat skończony



  1  Wejście:  - automat akceptujący język .
  2  Wyjście:  -- wyrażenie regularne opisujące język .
  3  for each  
  4    for each  
  5      for each  
  6        "";                                 wyrażenie puste
  7        if  
  8          if ""
  9            ;            podstawiamy wyrażenie regularne
 10          else
 11            ;       podstawiamy wyrażenie regularne
 12          end if
 13        end if
 14      end for
 15    end for
 16    if   and   then
 17      ;               podstawiamy wyrażenie regularne
 18    end if
 19  end for
 20  rozwiąż ;
 21  ;
 22  return ;



Funkcja rozwiąż w algorytmie Automat2Wr2 rozwiązuje układ równań (mający na podstawie wcześniejszych uwag jednoznaczne rozwiązania), zwraca obliczone języki , .

Rozwiązanie można wykonać metodą rugowania, przechodząc od do . Równanie rozwiązujemy, korzystając ze wzoru w lemacie Ardena (rolę w lemacie odgrywa ) i podstawiamy do pozostałych równań (tzn. równań dla ). Mając już wyliczone , wyliczamy kolejne idąc od do . Dla lepszego zrozumienia metody przedstawiamy następujący przykład.

Przykład 1.1.

Dany niech będzie automat pokazany na rysunku 1 (pominęliśmy tu dla uproszczenia jedną strzałkę wychodzącą ze stanu w celu uniknięcia zwiększenia liczby stanów, gdyż chcąc formalnie narysować automat deterministyczny, musielibyśmy dodać stan i zdefiniować , , ale widać, że wcale nie trzeba wtedy obliczać języka , gdyż z tego stanu nie da się już wyjść - jest to tzw. sink state).

Rysunek 1

Ułóżmy równania do naszego układu równań. Mamy:


Mamy więc . Korzystając z lematu Ardena, otrzymujemy . Podstawiając obliczone do równania i obliczając pozostałe , otrzymujemy ostatecznie:

Ponieważ , rozwiązaniem jest:

Ćwiczenie 3

Niech dany będzie automat o następującej funkcji przejść:

Wykorzystując algorytm Automat2WR2, wyznacz wyrażenie regularne odpowiadające językowi akceptowanemu przez .

Rozwiązanie

Ćwiczenie 4

Dane niech będą automaty: -stanowy i -stanowy , oba nad alfabetem i akceptujące odpowiednio języki i . Pokaż, że problem stwierdzenia, czy dla dowolnego zachodzi , jest rozstrzygalny:

  1. poprzez skonstruowanie niedeterministycznego automatu posiadającego stanów,
  2. poprzez skonstruowanie deterministycznego automatu -stanowego.
Rozwiązanie punktu 1
Rozwiązanie punktu 2

Ćwiczenie 5

Skonstruuj algorytm (oraz określ jego złożoność) dla następującego problemu (tym samym dowodząc jego rozstrzygalności):

Dany jest automat . Czy ?

Rozwiązanie


ZADANIA DOMOWE

Ćwiczenie 6

Zastosuj algorytm Automat2GReg do automatu o następującej funkcji przejść:

gdzie jest stanem początkowym oraz .

Ćwiczenie 7

Zbuduj automaty akceptujące języki generowane następującymi gramatykami ( oznaczają symbole nieterminalne, -- terminalne):

1. , , , , , , , .

2. , , , , , .

Ćwiczenie 8

Zbuduj automaty (z pustymi przejściami) akceptujące poniższe języki:

  1. ,
  2. ,
  3. .
Wskazówka

Ćwiczenie 9

Niech dany będzie automat o następującej funkcji przejść:

Wykorzystując algorytm Automat2WR2, wyznacz wyrażenie regularne odpowiadające językowi akceptowanemu przez .

Ćwiczenie 10

Skonstruuj algorytmy dla następujących problemów rozstrzygalnych:

  1. Równoważność dowolnych automatów i .
  2. Nieskończoność języka dla dowolnego automatu .
Wskazówka do punktu 1
Wskazówka do punktu 2