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

Ćwiczenie 0.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 0.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$.

1. $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

(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$.

Wyjście: $r$ -- wyrażenie regularne opisujące język $L$.

for each $s\in S$

for each $t\in S$

for each Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle a \in A\displaystyle L_s \leftarrow "";\displaystyle \triangleright} wyrażenie puste if $f(t,a)=s$

if Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L_s=""\displaystyle L_s \leftarrow L_ta} ; $▹$ podstawiamy wyrażenie regularne else $L_s\leftarrow L_s+L_{t}a$; $▹$ podstawiamy wyrażenie regularne endif endif

endfor

endfor

if $s=s_0$ and $s\in T{L}_s\leftarrow L_s+1$; $▹$ podstawiamy wyrażenie regularne

endif

endfor

rozwiąż $\{L_i=\sum _{t\in S}{L}_t{\}}_{i=0,...,|S|-1}$;

$r\leftarrow \sum _{s_i\in T}{L}_i$;

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

Dany niech będzie automat pokazany na rysunku Uzupelnic ja-lekcja8-c-rys1| (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 ja-lekjca8-c-rys1

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

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

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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 ${𝒜}$ 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 Uzupelnic ja-lekcja7-c-cw1.1|

Ćwiczenie

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

---

{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$.

Wyjście: Odpowiedź true (tak) lub false (nie).

Zaznacz$(s_0)$;

for each $s\in T$

if $\text{<mrow data-mjx-texclass="ORD">zaznaczone</mrow>}[s]=1$ return false endif

endfor

return true;

Algorytm

---

[1] procedure Zaznacz($s\in S$)

$\text{<mrow data-mjx-texclass="ORD">zaznaczone</mrow>}[s]\leftarrow 1$;

for each $a\in A$

if zaznaczone$[f(s,a)]\ne 1$ Zaznacz$(f(s,a))$; endif

endfor

end procedure

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|)$.

ZADANIA DOMOWE

Ćwiczenie

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

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$.

1. $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

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

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

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

1. Równoważność dowolnych automatyó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 Uzupelnic cw_ai|. Jaki warunek muszą spełniać stany $s\in S_A,t\in S_B$, aby $(s,t)\in T$?

WSKAZÓWKI 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.).

1. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \exists s \in S, w_1, w_2 \in A^*:\ f(s_0, w_1)=s \wedge f(s,w_2)=s...}

Ćwiczenie

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

Dla automatów ${𝒜}=(S_A,A,f_A,s_A^0,T_A)$ oraz ${ℬ}=(S_B,A,f_B,s_B^0,T_B)$ konstruujemy następujący automat ${𝒞}=(S,A,f,s_0,T)$:

• $S=S_A\times S_B,$
• $s_0=(s_A^0,s_B^0),$
• $T=\{(s,t):s\in T_A,t\in T_B\}$
• $f((s,t),a)=(f_A(s,a),f_B(s,a)).$

Zachodzi

$w\in L({𝒜})\cap L({ℬ})⟺w\in L({𝒞}).$