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

Ćwiczenie 1

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

$\begin{array}{ccccc}f& s_0& s_1& s_2& s_3\\ a& s_1& s_2& s_0& s_2\\ b& s_3& s_2& s_2& s_2\end{array}$

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

Rozwiązanie

Pętla w liniach 7.--17. do zbioru $P$ doda następujące produkcje: $v_0\to a{v}_1$, $v_0\to b{v}_3$, $v_1\to a{v}_2$, $v_1\to b{v}_2$, $v_2\to a{v}_0$, $v_2\to b{v}_2$, $v_3\to a{v}_2$, $v_3\to b{v}_2$. Ponieważ stanami końcowymi są $s_0$ i $s_2$, w pętli (w liniach 12.--14.) dodane zostaną jeszcze produkcje $v_0\to 1$ oraz $v_2\to 1$.

Ćwiczenie 2

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

1. $v_0\to a{v}_0$, $v_0\to b{v}_1$, $v_0\to b{v}_2$, $v_1\to b{v}_0$, $v_1\to a{v}_2$, $v_2\to a{v}_0$, $v_2\to 1$.

2. $v_0\to a{v}_1$, $v_0\to b$, $v_1\to b{v}_0$, $v_1\to a{v}_1$, $v_1\to 1$.

Rozwiązanie punktu 1

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

$f(s_0,a)=\{f_0\}$, $f(s_0,b)=\{s_1,s_2\}$, $f(s_1,b)=\{s_0,s_2\}$, $f(s_2,a)=s_0$. Ponieważ w gramatyce istnieje produkcja $v_2\to 1$, stan $s_2$ oznaczamy jako końcowy.

Rozwiązanie punktu 2

Ponieważ w gramatyce występuje produkcja $v_0\to 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: $v_0\to b{v}_k$ oraz $v_k\to 1$. Teraz możemy skonstruować automat. Jego zbiór stanów to $s_0,s_1,s_k$, stanem początkowym jest $s_0$, a funkcja przejść zdefiniowana jest następująco:

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

Ponieważ w gramatyce wystąpiły produkcje $v_1\to 1$ oraz $v_k\to 1$, stany $v_1$ oraz $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 ${𝒜}=(S,A,f,s_0,T)$. Chcemy zbudować wyrażenie regularne opisujące język akceptowany przez ${𝒜}$. Do wyprowadzenia metody potrzebować będziemy lematu Ardena.

Lemat 0.1. [Arden]

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

posiada jedyne rozwiązanie $X=S{R}^{*}$, które jest językiem regularnym.

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

akceptowane przez

${𝒜}$

, gdyby stanem końcowym był stan

$s_i$

, tzn. gdyby

$T=\{s_i\}$

:

$L_i=\{w\in A^{*}:f(s_0,w)=s_i\}$.

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

$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 $L_i=\sum _{j\in I}{L}_j{a}_j$, $I=\{i_1,i_2,...,i_n\}$ , gdzie $L_i$ traktowane są jak niewiadome. Następnie układ taki rozwiążemy ze względu na każdą zmienną $L_i$ (tu pomocny będzie lemat Ardena). Szukanym przez nas wyrażeniem regularnym będzie wyrażenie postaci $\sum _{i\in I}{L}_i$, gdzie $I$ jest zbiorem indeksów $i$ stanów końcowych $s_i$ 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: ${𝒜}=(S,A,f,s_0,T)$ - automat akceptujący język $L$.
  2  Wyjście: $r$ -- wyrażenie regularne opisujące język $L$.
  3  for each $s\in S$ 
  4    for each $t\in S$ 
  5      for each  $a\in A$
  6        $L_s\leftarrow$"";                                $▹$ wyrażenie puste
  7        if $f(t,a)=s$ 
  8          if $L_s=$""
  9            $L_s\leftarrow L_{t}a$;           $▹$ podstawiamy wyrażenie regularne
 10          else
 11            $L_s\leftarrow L_s+L_{t}a$;      $▹$ podstawiamy wyrażenie regularne
 12          end if
 13        end if
 14      end for
 15    end for
 16    if $s=s_0$  and  $s\in T$ then
 17      $L_s\leftarrow L_s+1$;              $▹$ podstawiamy wyrażenie regularne
 18    end if
 19  end for
 20  rozwiąż $\{L_i=\sum _{t\in S}{L}_t{\}}_{i=0,...,|S|-1}$;
 21  $r\leftarrow \sum _{s_i\in T}{L}_i$;
 22  return $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 $L_i$, $i=0,...,|S|-1$.

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

$\{\begin{array}{l}{L}_0=L_{0}b+L_{2}b+1\\ L_1=L_{0}a+L_{1}a\\ L_2=L_{1}b\end{array}\iff \{\begin{array}{l}{L}_0=L_{0}b+L_{1}bb+1\\ L_1=L_{0}a+L_{1}a\\ \end{array}\iff L_0=L_{0}b+L_{0}a{a}^{*}b{b}^{*}+1$

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

$\{\begin{array}{l}{L}_0=(b+a^{+}bb{)}^{*}\\ L_1=(b+a^{+}bb{)}^{*}{a}^{+}\\ L_2=(b+a^{+}bb{)}^{*}{a}^{+}b.\end{array}$

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

$w=L_0+L_1+L_2=(b+a^{+}bb{)}^{*}(1+a^{+}(1+b))$.

Ćwiczenie 3

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

$\begin{array}{ccccc}f& s_0& s_1& s_2& s_3\\ a& s_1& s_2& s_0& s_3\\ b& s_3& s_2& s_2& s_3\end{array}$

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

Rozwiązanie

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

$\{\begin{array}{l}{L}_0=L_{2}a+1\\ L_1=L_{0}a\\ L_2=L_1(a+b)+L_{2}b\end{array}$

W równaniu drugim zamieniamy $L_0$ na $L_{2}a+1$ i otrzymujemy

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

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

$L_0=(a^2+ab)(a^3+a^{2}b+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:

$L_0=(a(a+b)b^{*}a{)}^{*}$.

Ćwiczenie 4

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

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

Rozwiązanie punktu 1

Niech ${𝒜}=(S_A,A,f_A,s_A^0,T_A)$ oraz ${ℬ}=(S_B,A,f_B,s_B^0,T_B)$ będą zadanymi automatami. Konstruujemy automat ${𝒞}=(S,A,f,s_0,T)$ taki, że $S=S_A\cup S_B\mathrm{\setminus }\{s_B^0\}$, $s_0=s_A^0$, $T=T_B$, gdy $s_B^0\in ̸T_B$, $T=T_B\cup T_A$, gdy $s_B^0\in T_B$, a funkcja przejść $f$ jest zdefiniowana następująco:

$\begin{array}{rl}\mathrm{\forall }s\in S_A,a\in Af(s,a)& =f_A(s,a)\\ \mathrm{\forall }s\in S_B\mathrm{\setminus }\{s_B^0\},a\in Af(s,a)& =f_B(s,a)\\ \mathrm{\forall }s\in T_A,a\in Af(s,a)& =f(s_B^0,a).\end{array}$

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

$w\in L({𝒜})\cap L({ℬ})⟺ww\in L({𝒞})\wedge f(s_0,w)\cap T_A=\mathrm{\varnothing }$.

Oba warunki występujące po prawej stronie równoważności są algorytmicznie weryfikowalne i da się je sprawdzić w czasie $O(|w|)$. Konstrukcja automatu ${𝒞}$ w oczywisty sposób również jest algorytmizowalna i da się ją wykonać w czasie $O(|A|(n_A+n_B))$. Ponieważ $|S|=n_A+n_B-1$, więc ${𝒞}$ posiada $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 ${𝒜}=(S,A,f,s_0,T)$. Czy $L({𝒜})=\mathrm{\varnothing }$?

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 $O(|A|\cdot |S|)$ - liniowa ze względu na ilość stanów automatu. Złożoność pamięciowa także wynosi $O(|A|\cdot |S|)$.

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

---

 1  Wejście: ${𝒜}=(S,A,f,s_0,T)$ - deterministyczny automat akceptujący język $L$.
 2  Wyjście: Odpowiedź true (tak) lub false (nie).
 3  ZAZNACZ$(s_0)$;
 4  for each $s\in T$ 
 5    if $\text{<mrow data-mjx-texclass="ORD">zaznaczone</mrow>}[s]=1$ 
 6      return false
 7    end if
 8  end for
 9  return true;

 1  procedure Zaznacz($s\in S$)
 2  $\text{<mrow data-mjx-texclass="ORD">zaznaczone</mrow>}[s]\leftarrow 1$;
 3  for each  $a\in A$ 
 4    if zaznaczone$[f(s,a)]\ne 1$ 
 5      ZAZNACZ$(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ść:

$\begin{array}{ccccc}f& s_0& s_1& s_2& s_3\\ a& s_1& s_3& s_3& s_3\\ b& s_2& s_2& s_0& s_0\end{array}$

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

Ćwiczenie 7

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

1. $v_0\to a{v}_1$, $v_0\to b{v}_2$, $v_0\to b{v}_0$, $v_1\to b{v}_1$, $v_1\to a{v}_0$, $v_2\to b{v}_0$, $v_2\to b{v}_2$, $v_2\to 1$.

2. $v_0\to b{v}_2$, $v_0\to b$, $v_1\to b{v}_0$, $v_1\to a{v}_1$, $v_1\to 1$, $v_2\to a{v}_1$.

Ćwiczenie 8

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

1. $b((a+b{)}^{*}+a)$,
2. $(a+b{)}^{*}(a^{*}{b}^{*})$,
3. $a(b^{*}{a}^{*}{)}^{*}+1$.

Wskazówka

Zastosuj algorytm WR2Automat.

Ćwiczenie 9

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

$\begin{array}{ccccc}f& s_0& s_1& s_2& s_3\\ a& s_1& s_2& s_0& s_2\\ b& s_3& s_2& s_2& s_2\end{array}$

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 $L({𝒜})$ dla dowolnego automatu ${𝒜}$.

Wskazówka do punktu 1

Metoda pierwsza: istnieje dokładnie jeden automat minimalny. Metoda druga: rozważ automat akceptujący przecięcie $L({𝒜})\cap L({ℬ})$ tak jak w punkcie (2) zadania 4. punkt 2. Jaki warunek muszą spełniać stany $s\in S_A,t\in S_B$, aby $(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. $\mathrm{\exists }s\in S,w_1,w_2\in A^{*}:f(s_0,w_1)=s\wedge f(s,w_2)=s..$.