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

From Studia Informatyczne

Ćwiczenie 1

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

\displaystyle \begin{array} {c|c|c|c|c|} f & s_0 & s_1 & s_2 & s_3\\ \hline a & s_1 & s_2 & s_0 & s_2\\ \hline b & s_3 & s_2 & s_2 & s_2\\ \hline \end{array}

gdzie \displaystyle s_0 jest stanem początkowym oraz \displaystyle T=\{s_0,s_2\}.

Rozwiązanie

Pętla w liniach 7.--17. do zbioru \displaystyle P doda następujące produkcje: \displaystyle v_0 \rightarrow av_1, \displaystyle v_0 \rightarrow bv_3, \displaystyle v_1 \rightarrow av_2, \displaystyle v_1 \rightarrow bv_2, \displaystyle v_2 \rightarrow av_0, \displaystyle v_2 \rightarrow bv_2, \displaystyle v_3 \rightarrow av_2, \displaystyle v_3 \rightarrow bv_2. Ponieważ stanami końcowymi są \displaystyle s_0 i \displaystyle s_2, w pętli (w liniach 12.--14.) dodane zostaną jeszcze produkcje \displaystyle v_0 \rightarrow  1 oraz \displaystyle v_2 \rightarrow 1.

Ćwiczenie 2

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

1. \displaystyle v_0 \rightarrow av_0, \displaystyle v_0 \rightarrow bv_1, \displaystyle v_0 \rightarrow bv_2, \displaystyle v_1 \rightarrow bv_0, \displaystyle v_1 \rightarrow av_2, \displaystyle v_2 \rightarrow av_0, \displaystyle v_2 \rightarrow 1.

2. \displaystyle v_0 \rightarrow av_1, \displaystyle v_0 \rightarrow b, \displaystyle v_1 \rightarrow bv_0, \displaystyle v_1 \rightarrow av_1, \displaystyle v_1 \rightarrow 1.

Rozwiązanie punktu 1

Postępując zgodnie z algorytmem GReg2Automat, obliczamy funkcję przejść tworzonego automatu (w tym przypadku niedeterministycznego) o stanach \displaystyle s_0, s_1, s_2 (stanem początkowym jest \displaystyle s_0):

\displaystyle f(s_0,a)=\{f_0\}, \displaystyle f(s_0,b)=\{s_1,s_2\}, \displaystyle f(s_1,b)=\{s_0,s_2\},

\displaystyle f(s_2,a)=s_0. Ponieważ w gramatyce istnieje produkcja \displaystyle v_2 \rightarrow 1, stan \displaystyle s_2 oznaczamy jako końcowy.

Rozwiązanie punktu 2

Ponieważ w gramatyce występuje produkcja \displaystyle v_0 \rightarrow b, która ma postać niezgodną z postacią produkcji będących wejściem algorytmu, przekształcamy gramatykę, usuwając tę produkcję i dodając dwie inne: \displaystyle v_0 \rightarrow bv_k oraz \displaystyle v_k \rightarrow 1. Teraz możemy skonstruować automat. Jego zbiór stanów to \displaystyle s_0, s_1, s_k, stanem początkowym jest \displaystyle s_0, a funkcja przejść zdefiniowana jest następująco:

\displaystyle f(s_0,a)= s_1, \displaystyle f(s_0,b)=s_k, \displaystyle f(s_1,a)=s_1, \displaystyle s(s_1,b)=s_0.

Ponieważ w gramatyce wystąpiły produkcje \displaystyle v_1 \rightarrow 1 oraz

\displaystyle v_k \rightarrow 1, stany \displaystyle v_1 oraz \displaystyle v_k są stanami końcowymi.

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 \displaystyle \mathcal{A}=(S, A, f, s_0, T). Chcemy zbudować wyrażenie regularne opisujące język akceptowany przez \displaystyle \mathcal{A}. Do wyprowadzenia metody potrzebować będziemy lematu Ardena.

Lemat 0.1. [Arden]

Niech \displaystyle R \subseteq A^+ i \displaystyle S \subseteq A^* będą językami regularnymi. Wtedy równanie
\displaystyle X = XR + S

posiada jedyne rozwiązanie \displaystyle X=SR^*, które jest językiem regularnym.

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

akceptowane przez \displaystyle \mathcal{A}, gdyby stanem końcowym był stan \displaystyle s_i, tzn. gdyby \displaystyle T=\{s_i\}:
\displaystyle L_i=\{w \in A^*:\ f(s_0,w)=s_i\}.

Zauważmy, że jeśli do stanu \displaystyle s_t wchodzą strzałki prowadzące ze stanów \displaystyle s_{i_1}, s_{i_2}, ..., s_{i_n} odpowiednio z etykietami \displaystyle a_1, a_2,..., a_n (i tylko takie), to

\displaystyle L_t=\sum_{j=1}^n L_{i_j}a_j.

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 \displaystyle L_i=\sum_{j \in I}L_ja_j, \displaystyle I=\{i_1,i_2,...,i_n\} , gdzie \displaystyle L_i traktowane są jak niewiadome. Następnie układ taki rozwiążemy ze względu na każdą zmienną \displaystyle L_i (tu pomocny będzie lemat Ardena). Szukanym przez nas wyrażeniem regularnym będzie wyrażenie postaci \displaystyle \sum_{i\in I}L_i, gdzie \displaystyle I jest zbiorem indeksów \displaystyle i stanów końcowych \displaystyle s_i automatu \displaystyle \mathcal{A}.

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: \displaystyle \mathcal{A}=(S, A, f, s_0, T) - automat akceptujący język \displaystyle L.
  2  Wyjście: \displaystyle r -- wyrażenie regularne opisujące język \displaystyle L.
  3  for each \displaystyle s \in S 
  4    for each \displaystyle t \in S 
  5      for each  \displaystyle a \in A
  6        \displaystyle L_s \leftarrow "";                                \displaystyle      \triangleright wyrażenie puste
  7        if \displaystyle f(t,a)=s 
  8          if \displaystyle L_s=""
  9            \displaystyle L_s \leftarrow L_ta;           \displaystyle \triangleright podstawiamy wyrażenie regularne
 10          else
 11            \displaystyle L_s \leftarrow L_s + L_ta;      \displaystyle \triangleright podstawiamy wyrażenie regularne
 12          end if
 13        end if
 14      end for
 15    end for
 16    if \displaystyle s=s_0  and  \displaystyle s \in T then
 17      \displaystyle L_s \leftarrow L_s + 1;              \displaystyle \triangleright podstawiamy wyrażenie regularne
 18    end if
 19  end for
 20  rozwiąż \displaystyle \{L_i = \sum_{t \in S} L_t \}_{i=0,...,|S|-1};
 21  \displaystyle r \leftarrow \sum_{s_i \in T} L_i;
 22  return \displaystyle r;



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 \displaystyle L_i, \displaystyle i=0, ..., |S|-1.

Rozwiązanie można wykonać metodą rugowania, przechodząc od \displaystyle L_n do \displaystyle L_1. Równanie \displaystyle L_i=\sum_{t \in S} L_t rozwiązujemy, korzystając ze wzoru w lemacie Ardena (rolę \displaystyle X w lemacie odgrywa \displaystyle L_i) i podstawiamy do pozostałych równań (tzn. równań dla \displaystyle i=0,\dots,i-1). Mając już wyliczone \displaystyle L_0, wyliczamy kolejne \displaystyle L_i idąc od \displaystyle 1 do \displaystyle |S|-1. 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 \displaystyle s_2 w celu uniknięcia zwiększenia liczby stanów, gdyż chcąc formalnie narysować automat deterministyczny, musielibyśmy dodać stan \displaystyle s_3 i zdefiniować \displaystyle f(s_2, a)=s_3, \displaystyle f(s_3,a)=f(s_3,b)=s_3, ale widać, że wcale nie trzeba wtedy obliczać języka \displaystyle L_3, 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:


\displaystyle  \left\{ \begin{array} {l} L_0 = L_0b + L_2b + 1 \\ L_1 = L_0a +  L_1a \\ L_2 = L_1b \end{array}  \right. \Leftrightarrow \left\{ \begin{array} {l} L_0 = L_0b + L_1bb + 1 \\ L_1 = L_0a + L_1a \\ \end{array}  \right. \Leftrightarrow L_0=L_0b+L_0aa^*bb^*+1

Mamy więc \displaystyle L_0=L_0(b+a^+bb) + 1. Korzystając z lematu Ardena, otrzymujemy \displaystyle L_0=1(b+a^+bb)^*=(b+a^+bb)^*. Podstawiając obliczone \displaystyle L_0 do równania i obliczając pozostałe \displaystyle L_i, otrzymujemy ostatecznie:

\displaystyle  \left\{ \begin{array} {l} L_0 = (b+a^+bb)^* \\ L_1 = (b+a^+bb)^*a^+ \\ L_2 = (b+a^+bb)^*a^+b. \end{array}  \right.

Ponieważ \displaystyle T=\{s_0,s_1,s_2\}, rozwiązaniem jest:

\displaystyle w=L_0+L_1+L_2=(b+a^+bb)^*(1 + a^+(1 + b)).

Ćwiczenie 3

Niech dany będzie automat \displaystyle \mathcal{A}(S=\{s_0,s_1,s_2,s_3\},A=\{a,b\},f,s_0,T=\{s_0\}) o następującej funkcji przejść:

\displaystyle \begin{array} {c|c|c|c|c|} f & s_0 & s_1 & s_2 & s_3\\ \hline a & s_1 & s_2 & s_0 & s_3\\ \hline b & s_3 & s_2 & s_2 & s_3\\ \hline \end{array}

Wykorzystując algorytm Automat2WR2, wyznacz wyrażenie regularne odpowiadające językowi akceptowanemu przez \displaystyle \mathcal{A}.

Rozwiązanie

Po pierwsze zauważmy, że w obliczeniach nie musimy uwzględniać stanu \displaystyle s_3 ani języka \displaystyle L_3 stowarzyszonego z tym stanem. Układ równań będzie więc posiadał 3 równania o 3 niewiadomych \displaystyle L_0, \displaystyle L_1 oraz \displaystyle L_2:

\displaystyle  \left\{ \begin{array} {l} L_0 = L_2a+1 \\ L_1 = L_0a \\ L_2 = L_1(a+b)+L_2b \end{array}  \right.

W równaniu drugim zamieniamy \displaystyle L_0 na \displaystyle L_2a+1 i otrzymujemy

\displaystyle  \left\{ \begin{array} {l} L_1 = (L_2a+1)a = L_2a^2+a \\ L_2 = L_1(a+b)+L_2b. \end{array}  \right.
Teraz \displaystyle L_1 w równaniu drugim zastępujemy prawą stroną równania pierwszego:
\displaystyle L_2 = L_1(a+b)+L_2b = (L_2a^2+a)(a+b)+L_2b = L_2(a^3+a^2b+b)+a^2+ab.

Korzystamy z lematu Ardena i otrzymujemy \displaystyle L_2=(a^2+ab)(a^3+a^2b+b)^*. Podstawiamy to do równania \displaystyle L_0=L_2a+1 i otrzymujemy ostatecznie:

\displaystyle L_0=(a^2+ab)(a^3+a^2b+b)^*a+1= (a^2+ab)(a^2(a+b)+b)^*a+1.

Można pokazać, że wyrażenie to jest równoważne następującemu:

\displaystyle L_0=(a(a+b)b^*a)^*.

Ćwiczenie 4

Dane niech będą automaty: \displaystyle n_A-stanowy \displaystyle \mathcal{A} i \displaystyle n_B-stanowy \displaystyle \mathcal{B}, oba nad alfabetem \displaystyle A i akceptujące odpowiednio języki \displaystyle L(\mathcal{A}) i \displaystyle L(\mathcal{B}). Pokaż, że problem stwierdzenia, czy dla dowolnego \displaystyle w \in A^* zachodzi \displaystyle w \in L(\mathcal{A}) \cap L(\mathcal{B}), jest rozstrzygalny:

  1. poprzez skonstruowanie niedeterministycznego automatu posiadającego \displaystyle O(n_A+n_B) stanów,
  2. poprzez skonstruowanie deterministycznego automatu \displaystyle n_A \cdot n_B-stanowego.

Rozwiązanie punktu 1

Niech \displaystyle \mathcal{A}=(S_A, A, f_A, s_A^0, T_A) oraz \displaystyle \mathcal{B}=(S_B, A, f_B, s_B^0, T_B) będą zadanymi automatami. Konstruujemy automat \displaystyle \mathcal{C}=(S, A, f, s_0, T) taki, że \displaystyle S = S_A \cup S_B \backslash \{s_B^0\}, \displaystyle s_0=s_A^0, \displaystyle T=T_B, gdy \displaystyle s_B^0 \not \in T_B, \displaystyle T=T_B \cup T_A, gdy \displaystyle s_B^0 \in T_B, a funkcja przejść \displaystyle f jest zdefiniowana następująco:

\displaystyle \aligned \forall s \in S_A, a \in A\  f(s,a) &=f_A(s,a) \\ \forall s \in S_B \backslash \{s_B^0\}, a \in A\ f(s,a) &= f_B(s,a) \\ \forall s \in T_A, a \in A\ f(s,a) &= f(s_B^0,a). \endaligned

Zbiór stanów końcowych automatu \displaystyle \mathcal{A} staje się więc zbiorem stanów początkowych dla automatu \displaystyle \mathcal{B}, przy czym, jeśli \displaystyle s_B^0 \in T_B, to każdy ze stanów \displaystyle T_A jest równocześnie stanem końcowym w automacie \displaystyle \mathcal{C}. Zauważ, że:

\displaystyle w \in L(\mathcal{A}) \cap L(\mathcal{B}) \Longleftrightarrow ww \in L(\mathcal{C}) \wedge f(s_0,w) \cap T_A \not = \emptyset.

Oba warunki występujące po prawej stronie równoważności są algorytmicznie weryfikowalne i da się je sprawdzić w czasie \displaystyle O(|w|). Konstrukcja automatu \displaystyle \mathcal{C} w oczywisty sposób również jest algorytmizowalna i da się ją wykonać w czasie \displaystyle O(|A|(n_A+n_B)). Ponieważ \displaystyle |S|=n_A+n_B-1, więc \displaystyle \mathcal{C} posiada \displaystyle O(n_A+n_B) stanów.

Rozwiązanie punktu 2

Skorzystaj z konstrukcji z ćwiczenia 1 z ćwiczeń 7

Ć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 \displaystyle \mathcal{A}=(S, A, f, s_0, T). Czy \displaystyle L(\mathcal{A})=\emptyset?

Rozwiązanie

Bez straty ogólności możemy założyć, że automat jest deterministyczny. W algorytmie wykorzystamy procedurę Zaznacz przedstawioną poniżej.

Algorytm wykonuje przeszukanie automatu metodą DFS. Jego złożoność jest więc \displaystyle O(|A| \cdot |S|) - liniowa ze względu na ilość stanów automatu. Złożoność pamięciowa także wynosi \displaystyle O(|A| \cdot |S|).


Algorytm PustośćJęzyka - sprawdza, czy język akceptowany przez zadany automat jest pusty



 1  Wejście: \displaystyle \mathcal{A}=(S, A, f, s_0, T) - deterministyczny automat akceptujący język \displaystyle L.
 2  Wyjście: Odpowiedź true (tak) lub false (nie).
 3  ZAZNACZ\displaystyle (s_0);
 4  for each \displaystyle s \in T 
 5    if \displaystyle \textbf{zaznaczone}[s] = 1 
 6      return false
 7    end if
 8  end for
 9  return true;


 1  procedure Zaznacz(\displaystyle s \in S)
 2  \displaystyle \textbf{zaznaczone}[s] \leftarrow 1;
 3  for each  \displaystyle a \in A 
 4    if zaznaczone\displaystyle [f(s,a)]\neq 1 
 5      ZAZNACZ\displaystyle (f(s,a));
 6    end if
 7  end for
 8  end procedure



ZADANIA DOMOWE

Ćwiczenie 6

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

\displaystyle \begin{array} {c|c|c|c|c|} f & s_0 & s_1 & s_2 & s_3\\ \hline a & s_1 & s_3 & s_3 & s_3\\ \hline b & s_2 & s_2 & s_0 & s_0\\ \hline \end{array}

gdzie \displaystyle s_0 jest stanem początkowym oraz \displaystyle T=\{s_1\}.

Ćwiczenie 7

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

1. \displaystyle v_0 \rightarrow av_1, \displaystyle v_0 \rightarrow bv_2, \displaystyle v_0 \rightarrow bv_0, \displaystyle v_1 \rightarrow bv_1, \displaystyle v_1 \rightarrow av_0, \displaystyle v_2 \rightarrow bv_0, \displaystyle v_2 \rightarrow bv_2, \displaystyle v_2 \rightarrow 1.

2. \displaystyle v_0 \rightarrow bv_2, \displaystyle v_0 \rightarrow b, \displaystyle v_1 \rightarrow bv_0, \displaystyle v_1 \rightarrow av_1, \displaystyle v_1 \rightarrow 1, \displaystyle v_2 \rightarrow av_1.

Ćwiczenie 8

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

  1. \displaystyle b((a+b)^*+a),
  2. \displaystyle (a+b)^*(a^*b^*),
  3. \displaystyle a(b^*a^*)^*+1.

Wskazówka

Zastosuj algorytm WR2Automat.

Ćwiczenie 9

Niech dany będzie automat \displaystyle \mathcal{A}(S=\{s_0,s_1,s_2,s_3\},A=\{a,b\},f,s_0,T=\{s_0\}) o następującej funkcji przejść:

\displaystyle \begin{array} {c|c|c|c|c|} f & s_0 & s_1 & s_2 & s_3\\ \hline a & s_1 & s_2 & s_0 & s_2\\ \hline b & s_3 & s_2 & s_2 & s_2\\ \hline \end{array}

Wykorzystując algorytm Automat2WR2, wyznacz wyrażenie regularne odpowiadające językowi akceptowanemu przez \displaystyle \mathcal{A}.

Ćwiczenie 10

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

  1. Równoważność dowolnych automatów \displaystyle \mathcal{A} i \displaystyle \mathcal{B}.
  2. Nieskończoność języka \displaystyle L(\mathcal{A}) dla dowolnego automatu \displaystyle \mathcal{A}.

Wskazówka do punktu 1

Metoda pierwsza: istnieje dokładnie jeden automat minimalny. Metoda druga: rozważ automat akceptujący przecięcie \displaystyle L(\mathcal{A}) \cap L(\mathcal{B}) tak jak w punkcie (2) zadania 4. punkt 2. Jaki warunek muszą spełniać stany \displaystyle s \in  S_A, t \in S_B, aby \displaystyle (s,t) \in T?

Wskazówka do punktu 2

1. Automat akceptuje nieskończenie wiele słów, gdy w wyrażeniu regularnym odpowiadającym temu automatowi występuje gwiazdka Kleene'ego. Użyj metody z twierdzenia Kleene'ego (Twierdzenie 1.1, punkt 5.).

2. \displaystyle \exists s \in S, w_1, w_2 \in A^*:\ f(s_0, w_1)=s \wedge f(s,w_2)=s...