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.

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,\dots ,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 $f$ jest określona na $(s_i,a)$
 11        $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        end if
 15      end if
 16    end for
 17  end for
 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 1. Zbudujemy gramatykę, która będzie

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

Rysunek 1

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ć:

$\begin{array}{rlr}{v}_0& \to & a{v}_0|b{v}_1|1\\ v_1& \to & b{v}_1|a{v}_2\\ v_2& \to & a{v}_1|1\end{array}$

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 (patrz twierdzenie 2.2 wykład 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 \mathrm{\varnothing }$ 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.

---

  1  Wejście: $G=(V_N,V_T,P,v_0)$ - gramatyka regularna.
  2  Wyjście: ${𝒜}=(S,A,f,v_0,T)$ - automat taki, że $L({𝒜})=L(G)$.
  3  $S\leftarrow V_N$;
  4  $A\leftarrow V_T$;
  5  $T\leftarrow \mathrm{\varnothing }$;                                   $▹$ nie ma jeszcze stanów końcowych
  6  $s_0\leftarrow v_0$;
  7  $f\leftarrow \mathrm{\varnothing }$;                 $▹$ funkcja $f$ nie jest określona dla żadnego argumentu
  8  for each  $(v_i\to a_1{a}_2...a_n{v}_j)\in P$ do
  9    if $n>1$ then
 10      $V_N\leftarrow V_N\cup \{v^{a_1},...,v^{a_{n-1}}\}$;     $▹$ rozbijamy produkcję na kilka prostszych
 11      $P\leftarrow P\mathrm{\setminus }\{v_i\to a_1{a}_2...a_n{v}_j\}$;           $▹$ w tym celu usuwamy produkcję z $P$
 12      $P\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
 13      $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}}\}$;
 14    end if
 15  end for
 16    $▹$ wszystkie produkcje są postaci $u\to av$ lub $u\to 1$, gdzie $u,v\in V_N$, $a\in V_T$
 17  for each $(s_i\to a{s}_j)\in P$ do
 18    $f(s_i,a)\leftarrow s_j$;
 19  end for
 20  for each  $(v_i\to 1)\in P$ do
 21    $T\leftarrow T\cup \{v_i\}$;
 22  end for
 23  return ${𝒜}=(S,A,f,s_0,T)$;

Przykład 1.2

Jako wejście algorytmu rozważmy gramatykę z przykładu 1.1 (patrz przykład 1.1.) 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 1.

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 2 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 2

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 3 przedstawiono konstrukcje automatów akceptujących wyrażenia regularne $r+s$ (automat a)), $(rs)$ (automat b)) oraz $r^{*}$ (automat c)).

Rysunek 3

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 4. Korzeniem jest wierzchołek z małą wchodzącą strzałką.

Rysunek 4

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 2 lub 3. 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 2. Procedura JoinAutomata(type,${{ℳ}}_1,{{ℳ}}_2$) natomiast konstruuje na podstawie automatów ${{ℳ}}_1$, ${{ℳ}}_2$ automat z rysunku 2, 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 $\text{Root}(T)$ zwraca korzeń drzewa $T$, funkcje $\text{LeftChild}(T,v)$ oraz $\text{RightChild}(T,v)$ zwracają lewe i prawe dziecko wierzchołka $v$ (ew. NULL, gdy brak lewego lub prawego dziecka), natomiast funkcja $\text{Label}(T,v)$ zwraca etykietę wierzchołka $v$ drzewa $T$. Funkcja $\text{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

---

  1  Wejście: $r$ -- wyrażenie regularne.
  2  Wyjście: ${𝒜}=(S,A,f,s_0,T)$ -- automat rozpoznający język opisywany wyrażeniem $r$.
  3  $T\leftarrow \text{BuildTree}(r)$;
  4  $v_0\leftarrow \text{Root}(T)$;
  5  ${𝒜}\leftarrow$ PostOrder($T,v_0$);
  6  return ${𝒜}$;

Przykład 1.4

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

Plik:Ja-lekcja08-w-anim1.svg

Animacja 1

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

Rysunek 5

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.

Algorytm Procedure PostOrder

---

  1  procedure PostOrder ($T$: drzewo, $v$: wierzchołek)
  2  if IsLeaf($T,v$) then
  3    if $v$=NULL then
  4      ${{𝒜}}_v\leftarrow$ CreateAutomata('$a$');
  5    else
  6      if Label($T,v$)='1' then
  7        ${{𝒜}}_v\leftarrow$ CreateAutomata('$b$');
  8      else
  9        ${{𝒜}}_v\leftarrow$ CreateAutomata('$c$'); $▹$ Label$(T,v)\in A$
 10      end if
 11    end if
 12    return ${{𝒜}}_v$;
 13  else
 14    ${{𝒜}}_L\leftarrow$ PostOrder($T$,  LeftChild$(T,v)$);
 15    ${{𝒜}}_P\leftarrow$ PostOrder($T$, RightChild$(T,v)$);
 16    if Label($T,v$)='$+$' then 
 17      ${{𝒜}}_{LP}\leftarrow$JoinAutomata('$a$'$,{{𝒜}}_L,{{𝒜}}_P$);
 18    end if
 19    if Label($T,v$)='$\cdot$' then
 20      ${{𝒜}}_{LP}\leftarrow$JoinAutomata('$b$'$,{{𝒜}}_L,{{𝒜}}_P$);
 21    end if
 22    if Label($T,v$)='$*$' then
 23      ${{𝒜}}_{LP}\leftarrow$JoinAutomata('$c$'$,{{𝒜}}_L,{{𝒜}}_P$);
 24    end if
 25    return ${{𝒜}}_{LP}$;
 26  end if
 27  end procedure

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,\dots ,|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:

$\text{(1)}$

$\begin{array}{rl}{R}_{ij}^0& =\{\begin{array}{ll}\{a\in A:f(s_i,a)=s_j\}& \text{ dla }i=j,1⩽i,j⩽n\\ \{a\in Af(s_i,a)=s_j\}\cup \{1\}& \text{ dla }i=j,1⩽i,j⩽n\end{array}\\ R_{ij}^k& =R_{ik}^{k-1}(R_{kk}^{k-1}{)}^{*}{R}_{kj}^{k-1}\cup R_{ij}^{k-1},1⩽i,j,k⩽n.\end{array}$

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:

$\text{(2)}$

$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

$\text{(3)}$

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

---

  1  Wejście: ${𝒜}=(S=\{s_1,s_2,...,s_n\},A,f,s_1,T)$.
  2  Wyjście: $w$ - wyrażenie regularne opisujące język $L=L({𝒜})$.
  3  for $i\leftarrow 1$ to $n$ do
  4    for $j\leftarrow 1$ to $n$ do
  5      oblicz $r_{ij}^0$                            $▹$ stosujemy wzór (3);
  6    end for
  7  end for
  8  for $k\leftarrow 1$ to $n$ do
  9    for $i\leftarrow 1$ to $n$ do
 10      for $j\leftarrow 1$ to $n$ do
 11        $r_{ij}^k\leftarrow r_{ik}^{k-1}(r_{kk}^{k-1}{)}^{*}{r}_{kj}^{k-1}+r_{ij}^{k-1}$; $▹$ dokonujemy katenacji słów
 12      end for
 13    end for
 14  end for
 15  $r\leftarrow$ "";                           $▹$ podstaw pod $r$ słowo puste
 16  for $i\leftarrow 1$ to  $n$ 
 17    if $s_i\in T$ 
 18      if r="" 
 19        $r\leftarrow r_{1i}^n$;                     $▹$ stosujemy Twierdzenie 1.1
 20      else
 21        $r\leftarrow r+r_{1i}^n$;
 22      end if
 23    end if
 24  end for
 25  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 6.

Rysunek 6

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

	$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{)}^{*}$
$r_{13}^k$	$\varphi$	$\varphi$	$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{)}^{*})a^{+}+b{a}^{*}$
$r_{32}^k$	$\varphi$	$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$

Tabela 1. Obliczone wartości $r_{ij}^k$ dla automatu z rys. 6

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

$\begin{array}{rl}{r}_{13}^3& =r_{13}^2(r_{33}^2{)}^{*}{r}_{33}^2+r_{13}^2\\ & =a^{*}b(a^{+}b{)}^{*}b((a^{+}b+b{a}^{*}b)(a^{+}b{)}^{*}b+1{)}^{+}+a^{*}b(a^{+}b{)}^{*}b\\ & =a^{*}b(a^{+}b{)}^{*}b((a^{+}b+b{a}^{*}b)(a^{+}b{)}^{*}b{)}^{*}.\end{array}$

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

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

$L\ne \oslash :\iff :\mathrm{\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:

$w=v_{1}u{v}_2,u\ne 1,\mathrm{\forall }i=0,1,2\dots :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$ .

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

$w=v_{1}u{v}_2,:u\ne 1i{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.

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

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

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 ${𝒜}$

---

  1  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.
  2  Wyjście: Odpowiedź true (tak) lub false (nie).
  3  $k\leftarrow |w|$;
  4  $s\leftarrow s_0$;
  5  for $i\leftarrow 1$ to $k$ do
  6    $s\leftarrow f(s,w_i)$;
  7  end for
  8  if  $s\in T$ then
  9    return true;
 10  else
 11    return false;
 12  end if

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.