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

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

1. Dalsze algorytmy języków regularnych

Dowód twierdzenia z ostatniego wykładu, w którym udowodniliśmy równoważność rozpoznawania języka $L$ 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 $v$ tworzonej gramatyki odpowiada pewnemu stanowi $s_v$ automatu. Jeśli w automacie pod wpływem litery $a$ następuje przejście ze stanu $s_v$ do stanu $s_w$, to do zbioru praw gramatyki dodawane jest prawo $s_v\to a{s}_w$. Ponadto, jeśli stan $s_w$ jest stanem końcowym, to dodajemy także prawo $s_w\to 1$, 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: ${𝒜}=(S,A,f,s_0,T)$ -- automat niedeterministyczny.
  2  Wyjście: $G=(V_N,V_T,P,v_0)$ -- gramatyka regularna taka, że $L(G)=L({𝒜})$.
  3  $V_N\leftarrow \{v_0,v_1,...,v_{|S|-1}\}$;
  4  $V_T\leftarrow A$;
  5  $v_0\leftarrow s_0$;
  6  $P\leftarrow \mathrm{\varnothing }$;
  7  for each  $s_i\in S$ do
  8    for each  $a\in A$ do
  9      if $f(s_i,a)\ne$NULL then
 10        $s_j\leftarrow f(s_i,a)$; $▹$ funkcja
 11        $f$ jest określona na $(s_i,a)P\leftarrow P\cup \{s_i\to a{s}_j\}$;
 12        if $s_j\in T$ then
 13          $P\leftarrow P\cup \{s_j\to 1\}$;
 14        endif
 15      endif
 16    endfor
 17  endfor
 18  return $G$;

Oznaczmy przez $E({𝒜})$ ilość krawędzi w grafie $n$-stanowego automatu niedeterministycznego ${𝒜}$. Złożoność czasowa liczona względem $E({𝒜})$ jest liniowa i równa $O(E({𝒜}))$. Również złożoność pamięciowa jest liniowa i wynosi $O(|S|+E({𝒜}))$.

Przykład 1.1

Niech dany będzie automat ${𝒜}$ pokazany na rysunku Uzupelnic ja-lekcja8-w-rys1|. Zbudujemy gramatykę, która będzie

generowała język akceptowany przez ${𝒜}$.

<flash>file=ja-lekcja08-w-rys1.swf|width=250|height=150</flash>

<div.thumbcaption>ja-lekcja08-w-rys1

Ponieważ $f(s_0,a)=s_0$, a ponadto $s_0$ jest stanem końcowym, do $P$ dodajemy produkcje $v_0\to a{v}_0$ oraz $v_0\to 1$. Dodajemy także produkcję $v_0\to b{v}_1$, gdyż mamy $f(s_0,b)=s_1$.

Fakt, że $f(s_1,b)=s_1$ oraz $f(s_1,a)=s_2$ sprawia, że do $P$ dodajemy: $v_1\to b{v}_1$, $v_1\to a{v}_2$.

Ponieważ $f(s_2,a)=s_1$ do $P$ dodajemy: $v_2\to a{v}_1$ oraz $v_2\to 1$, gdyż $s_2\in T$.

Symbolem początkowym nowej gramatyki jest symbol $v_0$. Ostatecznie gramatyka ma postać: {-.5cm}

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned \nonumber v_0 & \rightarrow & av_0\ |\ bv_1 \ |\ 1\\ \nonumber v_1 & \rightarrow & bv_1\ |\ av_2 \\ \nonumber v_2 & \rightarrow & av_1\ |\ 1 \endaligned}

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 $v\to x$, gdzie $v\in V_N$, $x\in (V_N\cup V_T)$. Jeśli gramatyka zawiera takie produkcje, to możemy się ich łatwo pozbyć, zgodnie z Twierdzeniem 2.2 z Wykładu 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 $f\leftarrow$ 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 $v\to aw$, gdzie $v,w\in V_N,a\in V_T$.

Algorytm GReg2Automat -- buduje automat dla zadanej gramatyki regularnej.

---

Wejście: $G=(V_N,V_T,P,v_0)$ -- gramatyka regularna.

Wyjście: ${𝒜}=(S,A,f,v_0,T)$ -- automat taki, że $L({𝒜})=L(G)$.

$S\leftarrow V_N$;

$A\leftarrow V_T$;

$T\leftarrow$; $▹$ nie ma jeszcze stanów końcowych

$s_0\leftarrow v_0$;

$f\leftarrow$; $▹$ funkcja $f$ nie jest określona dla żadnego argumentu

for each $(v_i\to a_1{a}_2...a_n{v}_j)\in P$

if $n>1V_N\leftarrow V_N\cup \{v^{a_1},...,v^{a_{n-1}}\}$; $▹$ rozbijamy produkcję na kilka prostszych

$P\leftarrow P\mathrm{\setminus }\{v_i\to a_1{a}_2...a_n{v}_j\};▹$ w tym celu usuwamy produkcję z $PP\leftarrow P\cup \{v_i\to a_1{v}^{a_1},v^{a_{n-1}}\to a_n{v}_j\}$; $▹$ w zamian dodając ciąg krótszych

$P\leftarrow P\cup \{v^{a_1}\to a_2{v}^{a_2},\dots ,v^{a_{n-2}}\to a_{n-1}{v}^{a_{n-1}}\}$;

endif

endfor

$▹$ wszystkie produkcje są postaci $u\to av$ lub $u\to 1$, gdzie $u,v\in V_N$, $a\in V_T$

for each $(s_i\to a{s}_j)\in Pf(s_i,a)\leftarrow s_j$;

endfor

for each $(v_i\to 1)\in PT\leftarrow T\cup \{v_i\}$;

endfor

return ${𝒜}=(S,A,f,s_0,T)$;

Przykład 1.2

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

Mamy $S=\{s_0,s_1,s_2\}$. W liniach 17. -- 19. określana jest funkcja przejścia: $f(s_0,a)=s_0$, $f(s_0,b)=s_1$, $f(s_1,b)=s_1$, $f(s_1,a)=s_2$ oraz $f(s_2,a)=s_1$.

Pętla w liniach 20. -- 22. przebiega po dwóch produkcjach: $v_0\to 1$ oraz $v_2\to 1$, dodaje zatem do zbioru $T$ stanów końcowych stany $s_0$ oraz $s_2$. Szukany automat to automat z poprzedniego przykładu; przedstawiony jest na rysunku Uzupelnic ja-lekcja8-w-rys1|.

Automat powstały w wyniku działania algorytmu GReg2Automat nie musi być automatem deterministycznym (wystarczy, że w zbiorze produkcji znajdą się dwie produkcje postaci $v_i\to a{v}_j$ oraz $v_i\to a{v}_k$ dla pewnego $a\in A$), 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 $O(p)$, gdzie $p$ jest liczbą produkcji występujących w zbiorze praw $P$ 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 $a\in A,r,s\in {𝒲}{ℛ}$. Najpierw pokażemy, że językom odpowiadającym wyrażeniom regularnym , $1$, $a$, $r+s$, $rs$ oraz $r^{*}$ 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 Uzupelnic ja-lekcja8-w-rys3| przedstawione są trzy automaty. Automat a) rozpoznaje język pusty, automat b) -- język $\{1\}$, a automat c) -- język $\{a\}$, dla $a\in A$.

RYSUNEK ja-lekcja8-w-rys3

Niech dane będą automaty: $M_1$, akceptujący język opisywany wyrażeniem $r$ oraz $M_2$, akceptujący język opisywany wyrażeniem $s$. Na rysunku Uzupelnic ja-lekcja8-w-rys4| przedstawiono konstrukcje automatów akceptujących wyrażenia regularne $r+s$ (automat a)), $(rs)$ (automat b)) oraz $r^{*}$ (automat c)).

RYSUNEK ja-lekcja8-w-rys4

W automacie a) stan $q_0$ jest stanem początkowym, stan $f_0$ -- stanem końcowym, stany $q_1,q_2$ oraz $f_1,f_2$ oznaczają odpowiednio stany początkowe automatów $M_1$ i $M_2$ oraz stany końcowe automatów $M_1$ i $M_2$.

W automacie b) stan $q_0$ jest jednocześnie jego stanem początkowym oraz stanem początkowym automatu $M_1$, stan $f_1$ jest stanem końcowym automatu b) i jednocześnie stanem końcowym automatu $M_2$. Stan $f_0$ jest stanem końcowym w $M_1$, a $q_1$ -- początkowym w $M_2$.

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

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 $r=(a^{*}b)(ab+c)$. Drzewo odpowiadające $r$ przedstawione jest na rysunku Uzupelnic ja-lekcja6-w-rys3|. Korzeniem jest wierzchołek z małą wchodzącą strzałką.

RYSUNEK ja-lekcja8-w-rys5

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 $x$, a na końcu sam węzeł $x$. Dzięki temu, wchodząc do węzła $x$ drzewa etykietowanego daną operacją na wyrażeniu regularnym oba poddrzewa $P$ i $L$ wierzchołka $x$ będą już reprezentowane przez automaty ${{𝒜}}_P$ oraz ${{𝒜}}_L$. Teraz wystarczy zastosować jedną z konstrukcji z rysunku Uzupelnic ja-lekcja8-w-rys3| lub Uzupelnic ja-lekcja8-w-rys4|. 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,${{ℳ}}_1,{{ℳ}}_2$). Zmienna type może przyjmować wartości '$a$', '$b$' lub '$c$'. Funkcja zwraca automat CreateAutomata(type) przedstawiony (zależnie od zmiennej type) na rysunku Uzupelnic ja-lekcja8-w-rys3|. Procedura JoinAutomata(type,${{ℳ}}_1,{{ℳ}}_2$) natomiast konstruuje na podstawie automatów ${{ℳ}}_1$, ${{ℳ}}_2$ automat z rysunku Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle [[##ja-lekcja8-w-rys3|Uzupelnic ja-lekcja8-w-rys3|]]} , przy czym dla przypadku type=$c$ automat ${{ℳ}}_2$ 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 Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \displaystyle \textsc{Root}(T)} zwraca korzeń drzewa $T$, funkcje Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \displaystyle \textsc{LeftChild}(T,v)} oraz Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \displaystyle \textsc{RightChild}(T,v)} zwracają lewe i prawe dziecko wierzchołka $v$ (ew. NULL, gdy brak lewego lub prawego dziecka), natomiast funkcja Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \displaystyle \textsc{Label}(T,v)} zwraca etykietę wierzchołka $v$ drzewa $T$. Funkcja Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \displaystyle \textsc{IsLeaf}(T,v)} zwraca wartość $\text{<mrow data-mjx-texclass="ORD">true</mrow>}$, gdy $v$ jest liściem w drzewie $T$ oraz $\text{<mrow data-mjx-texclass="ORD">false</mrow>}$ w przypadku przeciwnym.

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

---

Wejście: $r$ -- wyrażenie regularne.

Wyjście: ${𝒜}=(S,A,f,s_0,T)$ -- automat rozpoznający język opisywany wyrażeniem $r$.

Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \displaystyle T\leftarrow \textsc{BuildTree}(r)} ;

Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \displaystyle v_0 \leftarrow \textsc{Root}(T)} ;

${𝒜}\leftarrow$ PostOrder($T,v_0$);

return ${𝒜}$;

Algorytm

---

procedure PostOrder ($T$: drzewo, $v$: wierzchołek)

if IsLeaf($T,v$)

if $v$=NULL ${{𝒜}}_v\leftarrow$ CreateAutomata('$a$');

else

if Label($T,v$)='1' ${{𝒜}}_v\leftarrow$ CreateAutomata('$b$');

else

${{𝒜}}_v\leftarrow$ CreateAutomata('$c$'); $▹$ Label$(T,v)\in A$

endif endif

return ${{𝒜}}_v$;

else

${{𝒜}}_L\leftarrow$ PostOrder($T$,Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \displaystyle \textsc{LeftChild}(T,v)} );

${{𝒜}}_P\leftarrow$ PostOrder($T$,Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \displaystyle \textsc{RightChild}(T,v)} );

if Label($T,v$)='$+$' ${{𝒜}}_{LP}\leftarrow$JoinAutomata('$a$'$,{{𝒜}}_L,{{𝒜}}_P$);

endif

if Label($T,v$)='$\cdot$' ${{𝒜}}_{LP}\leftarrow$JoinAutomata('$b$'$,{{𝒜}}_L,{{𝒜}}_P$);

endif

if Label($T,v$)='$*$' ${{𝒜}}_{LP}\leftarrow$JoinAutomata('$c$'$,{{𝒜}}_L,{{𝒜}}_P$);

endif

return ${{𝒜}}_{LP}$;

endif

end procedure

Przykład 1.4

Zastosujemy algorytm Wr2Automat do konstrukcji automatu dla wyrażenia regularnego $w=(a^{*}b)(ab+c)$.

ANIMACJA - opis w pliku ja-lekcja8-w-anim1.pdf

Automat ${{𝒜}}_{10}$ jest zwrócony przez algorytm jako automat akceptujący język opisywany wyrażeniem $r=(a^{*}b)(ab+c)$. Automat ten przedstawiony jest na rysunku Uzupelnic ja-lekcja8-w-rys6|

RYSUNEK ja-lekcja8-w-rys6

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.

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 ${𝒜}=(S,A,f,s_1,T)$. Zbudujemy wyrażenie regularne opisujące język akceptowany przez ${𝒜}$.

Konstrukcja polega na obliczeniu zbiorów $R_{ij}^k$ (definicja poniżej), gdzie $i,j=1,...,|S|$, co jest równoważne konstrukcji pewnych wyrażeń regularnych $r_{ij}^k$. Szukany język będzie odpowiadał sumie pewnych zbiorów $R_{ij}^k$, a zatem opisywany będzie przez wyrażenie regularne postaci $r_{i{j}_1}^k+...+r_{i{j}_t}^k$ dla pewnych $j_l$, $i$ oraz $k$.

Załóżmy, że zbiór stanów automatu jest postaci $S=\{s_1,s_2,...,s_n\}$. Wprowadźmy porządek na

zbiorze

$S$

, przyjmując:

$s_i\prec s_j\iff i<j.$

Zbiory $R_{ij}^k$ definiujemy w następujący sposób:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned R_{ij}^0 &= \left\{ \begin{array} {ll} \{a \in A:\ f(s_i,a)=s_j\} & \mbox{ dla } i \not = j,\ 1 \leqslant i,j \leqslant n \\ \{a \in A\ f(s_i, a)=s_j\} \cup \{ 1 \} & \mbox{ dla } i=j,\ 1 \leqslant i,j \leqslant n \end{array} \right. \\ \nonumber R_{ij}^k &= R_{ik}^{k-1}(R_{kk}^{k-1})^*R_{kj}^{k-1} \cup R_{ij}^{k-1},\ 1 \leqslant i,j,k \leqslant n. \endaligned}

Intuicyjnie, zbiór $R_{ij}^k$ to ogół wszystkich słów $w$ takich, że $f(s_i,w)=s_j$, a ponadto jeśli $w=a_1{a}_2...a_m$, to $\mathrm{\forall }1⩽j⩽m-1f(s_i,a_1{a}_2...a_j)=s_l\wedge l⩽k$.

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

$r_{ij}^k=r_{ik}^{k-1}(r_{kk}^{k-1}{)}^{*}{r}_{kj}^{k-1}+r_{ij}^{k-1},1⩽i,j,k⩽n.$

Pozostaje wyjaśnić jak wyglądają wyrażenia $r_{ij}^0$. Jeśli $R_{ij}^k=\{a_1,a_2,\dots ,a_s\}$ to

$r_{ij}^0=a_1+a_2+\dots +a_s$

Twierdzenie 1.1

Niech ${𝒜}$ oraz $R_{ij}^k$ będą zdefiniowane jak powyżej i niech zbiór stanów końcowych dla ${𝒜}$ ma postać $T=\{s_{j_1},s_{j_2},...,s_{j_t}\}$. Wtedy

$L({𝒜})=r_{1j_1}^n+r_{1j_2}^n+...+r_{1j_t}^n.$

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.

---

Wejście: ${𝒜}=(S=\{s_1,s_2,...,s_n\},A,f,s_1,T)$.

Wyjście: $w$ -- wyrażenie regularne opisujące język $L=L({𝒜})$.

for $i\leftarrow 1\text{<mrow data-mjx-texclass="ORD">to</mrow>}n$

for $j\leftarrow 1\text{<mrow data-mjx-texclass="ORD">to</mrow>}n$

oblicz $r_{ij}^0▹$ stosujemy wzór (Uzupelnic compute_rij0|);

endfor

endfor

for $k\leftarrow 1\text{<mrow data-mjx-texclass="ORD">to</mrow>}n$

for $i\leftarrow 1\text{<mrow data-mjx-texclass="ORD">to</mrow>}n$

for $j\leftarrow 1\text{<mrow data-mjx-texclass="ORD">to</mrow>}n{r}_{ij}^k\leftarrow r_{ik}^{k-1}(r_{kk}^{k-1}{)}^{*}{r}_{kj}^{k-1}+r_{ij}^{k-1}$; $▹$ dokonujemy katenacji słów

endfor

endfor

endfor

$r\leftarrow$ ""; $▹$ podstaw pod $r$ słowo puste

for $i\leftarrow 1\text{<mrow data-mjx-texclass="ORD">to</mrow>}n$

if $s_i\in T$

if r="" $r\leftarrow r_{1i}^n$; $▹$ stosujemy Twierdzenie Uzupelnic thm:FormOfL| else

$r\leftarrow r+r_{1i}^n$; endif

endif

endfor

return $r$;

Podczas obliczania wyrażeń $r_{ij}^k$ 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 Uzupelnic ja-lekcja8-w-rys7|.

<flash>file=ja-lekcja08-w-rys7.swf|width=250|height=250</flash>

<div.thumbcaption>ja-lekcja08-w-rys7

Mamy $|S|=3$, $i,j\in \{1,2,3\}$, $k\in \{0,1,2,3\}$, $T=\{s_3\}$. Szukamy zatem wyrażenia regularnego $r=r_{13}^3$.

Najpierw musimy obliczyć $r_{ij}^0$ dla wszystich $i,j\in \{1,2,3\}$. Mamy na przykład $r_{31}^0=a+b$, gdyż z definicji zachodzi: $R_{31}^0=\{a\in A:f(s_3,a)=s_1\}=\{a,b\}$.

Gdy mamy wyliczone wszystkie $r_{ij}^0$, przystępujemy do obliczeń dla $k=1$.

Na przykład:

$r_{31}^1=r_{31}^0(r_{11}^0{)}^{*}{r}_{11}^0+r_{31}^0=(a+b)(a+1{)}^{*}(a+1)+(a+b),$

co po zredukowaniu daje

$r_{31}^1=(a+b)(a+1{)}^{+}+(a+b)=(a+b)a^{*}+(a+b)=(a+b)a^{*}=a^{+}+b{a}^{*}.$

Obliczone wyrażenia $r_{ij}^k$ dla $k=0,1,2$ oraz dla wszystkich $i,j$ przedstawione są w tabeli Uzupelnic tab_rijk|.

[!hf]

Uzupelnij tytul

	$k=0$	$k=1$	$k=2$
$r_{11}^k$	$a+1$	$a^{*}$	$a^{*}b(a^{+}b{)}^{*}{a}^{+}+a^{*}$
$r_{12}^k$	$b$	$a^{*}b$	$a^{*}b(a^{+}b{)}^{*}+1$
$r_{13}^k$			$a^{*}b(a^{+}b{)}^{*}b$
$r_{21}^k$	$a$	$a^{+}$	$(a^{+}b{)}^{*}{a}^{+}$
$r_{22}^k$	$1$	$a^{+}b+1$	$(a^{+}b{)}^{*}$
$r_{23}^k$	$b$	$b$	$(a^{+}b{)}^{*}b$
$r_{31}^k$	$a+b$	$a^{+}+b{a}^{*}$	$(1+(a^{+}b+b{a}^{*}b)(a^{+}b+1))a^{+}+b{a}^{*}$
$r_{32}^k$		$a^{+}b+b{a}^{*}b$	$(a^{+}b+b{a}^{*}b)(a^{*}b{)}^{*}$
$r_{33}^k$	$1$	$1$	$(a^{+}b+b{a}^{*}b)(a^{*}b{)}^{*}b+1$

{Obliczone wartości $r_{ij}^k$ dla automatu z rys. Uzupelnic ja-lekcja8-w-rys7|}

Ponieważ $T=\{s_3\}$, szukanym wyrażeniem regularnym będzie $r=r_{13}^3$. Obliczamy zatem:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned \nonumber r_{13}^3 &= r_{13}^2(r_{33}^2)^*r_{33}^2+r_{13}^2 \\ \nonumber &= a^*b(a+b)^*b(a^+b+ba^*b)(a^*b)^*b+1)^*+a^*b(a^+b)^*b \\ \nonumber &= a^*b(a^+b)^*b((a^+b+ba^*b)(a^*b)^*b)^*. \endaligned}

2. 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 ${ℛ}{ℰ}{𝒢}(A^{*})$ następujące problemy są rozstrzygalne:

1. problem niepustości języka, $L\ne \mathrm{\varnothing },$
2. problem nieskończoności języka, $cardL={\mathrm{\aleph }}_0,$
3. problem równości języków, $L_1=L_2,$
4. problem należenia słowa do języka, $w\in L.$

Dowód

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L\neq \oslash \: \Leftrightarrow \: \exists w\in L\, :\, \mid w\mid <N,}

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle w=v_{1}uv_{2},\; \; u\neq 1,\; \; \forall i=0,1,2\ldots \: v_{1}u^{i}v_{2}\in L. }

Przyjmując teraz wartość $i=0$ , uzyskujemy:

$v_1{v}_2\in L,\mid v_1{v}_2\mid <\mid w\mid$

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

Uzupelnic nieskonczony|. Wystarczy udowodnić nastepującą równoważność:

$L\text{ nieskończony }⟺\mathrm{\exists }w\in L:N⩽\mid w\mid <2N.$

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

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle w=v_{1}uv_{2},\: u\neq 1\;\;\; i\;\;\; v_{1}u^{*}v_{2}\subset L}

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

Uzupelnic rownosc|. Rozważmy $L=(L_1\cap \overline{L_2})\cup (\overline{L_1}\cap L_2)$ . Język $L$ jest regularny, co wynika z domkniętości klasy ${{ℒ}}_3$ na operaje boolowskie. Równoważność

$L\ne \mathrm{\varnothing }⟺L_1\ne L_2.$

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

Uzupelnic nalezenie|. Konstruujemy automat ${𝒜}=(S,f,s_0,T)$ rozpoznający język $L$ i sprawdzamy, czy $f(s_0,w)\in T.$

$\mathrm{♢}$

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 $L$ akceptowanego przez zadany automat ${𝒜}$

---

Wejście: ${𝒜}=(S,A,f,s_0,T)$ -- automat akceptujący język $L$ oraz $w=w_1{w}_2\dots w_n\in A^{*}$ -- słowo.

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

$k\leftarrow |w|$;

$s\leftarrow s_0$;

for $i\leftarrow 1\text{<mrow data-mjx-texclass="ORD">to</mrow>}ks\leftarrow f(s,w_i)$;

endfor

if $s\in T$

return true;

else

return false;

endif

Algorytm działa w czasie $O(|w|)$ i posiada złożoność pamięciową $O(|A|\cdot |S|)$, 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.