Języki, automaty i obliczenia/Ćwiczenia 4: Wyrażenia regularne. Automat minimalny

Ćwiczenia 4

Ćwiczenie 1

Pokaż, że każdy skończony zbiór słów nad dowolnym alfabetem jest regularny, tzn. jest określony przez pewne wyrażenie regularne.

Rozwiązanie

Niech $L=\{w_1,w_2,...,w_n\}$ będzie skończonym zbiorem słów nad pewnym alfabetem $A$. Wtedy wyrażenie regularne

$\alpha =w_1+w_2+...+w_n$ jest wyrażeniem regularnym określającym zbiór $L$.

Ćwiczenie 2

Sprawdź, czy język $L$ ciągów binarnych, w których sekwencja 11 występuje dokładnie raz, da się określić wyrażeniem regularnym.

Rozwiązanie

Przykładowym wyrażeniem regularnym opisującym ten język

jest wyrażenie $(0^{*}+0^{*}10{)}^{*}11(0^{*}+00^{*}1{)}^{*}$.

Ćwiczenie 3

Udowodnij równoważności wyrażeń regularnych ($\alpha$, $\beta$ i $\gamma$ są dowolnymi wyrażeniami regularnymi).

(1) $\alpha +\alpha =\alpha$,

(2) $\alpha +\beta =\beta +\alpha$,

(3) $\alpha {\alpha }^{*}={\alpha }^{*}\alpha$,

(4) $({\alpha }^{*}{\beta }^{*}{)}^{*}=(\alpha +\beta {)}^{*}$,

(5) $(1+\alpha {)}^{*}={\alpha }^{*}$,

(6) $({\alpha }^{*}+{\beta }^{*}{)}^{*}=(\alpha +\beta {)}^{*}$.

Rozwiązanie punktu 1

Należy pokazać, że $|\alpha +\alpha |=|\alpha |$. Obliczamy: $|\alpha +\alpha |=|\alpha |\cup |\alpha |=|\alpha |$.

Rozwiązanie punku 2

$|\alpha +\beta |=|\alpha |\cup |\beta |=|\beta |\cup |\alpha |=|\beta +\alpha |$. Skorzystaliśmy tu z przemienności sumy mnogościowej.

Rozwiązanie punktu 3

$|\alpha {\alpha }^{*}|=|\alpha |\cdot |\alpha {|}^{*}=|\alpha {|}^{+}=|\alpha {|}^{*}\cdot |\alpha |=|{\alpha }^{*}\alpha |$.

Zauważ, że druga równość jest prawdziwa dlatego, że po obu stronach operatora katenacji występuje wyrażenie $\alpha$. Równość ta nie zachodzi w dowolnym przypadku, tzn. $|\alpha |\cdot |{\beta }^{*}|=|\beta |\cdot |\alpha {|}^{*}$.

Rozwiązanie punktu 4

Niech $L$ będzie językiem złożonym ze słów postaci $y=y_1{y}_2...y_n,n\ge 0$ takich, że każde $y_i$ należy do języka opisanego wyrażeniem regularnym $\alpha$ lub $\beta$. W oczywisty sposób $L$ opisany jest wyrażeniem regularnym $(\alpha +\beta {)}^{*}$. Zapiszmy teraz elementy $L$ w inny sposób: dla każdego $y=y_1...y_n\in L$ "pogrupujmy" wszystkie podsłowa $y_i$ należące do języka opisywanego wyrażeniem $\alpha$, które w słowie $y_1{y}_2...y_n$ występują obok siebie. To samo zróbmy ze słowami należącymi do języka opisywanego wyrażeniem $\beta$. Zatem $y=(y_a^1{y}_b^1)...(y_a^k{y}_b^k)$, gdzie każde $y_a^j$ należy do $|{\alpha }^{*}|$, a każde $y_b^j$ należy do $|{\beta }^{*}|$, gdyż każde $y_a^j$ ($y_b^j)$ może być katenacją dowolnej ilości słów należących do języka opisywanego wyrażeniem $\alpha$ (odpowiednio: $\beta$). W szczególności niektóre $y_a^j$ oraz $y_b^j$ mogą być słowami pustymi. Ponadto $k$ może być dowolnie duże. Zbiór słów $(y_a^1{y}_b^1)...(y_a^k{y}_b^k)$ jest więc opisywany wyrażeniem $({\alpha }^{*}{\beta }^{*}{)}^{*}$, przy czym wyrażenie w nawiasie "odpowiada" pojedynczej sekwencji $y_a^j{y}_b^j$, a gwiazdka przy nawiasie "odpowiada" konkatenacji dowolnej ilości takich słów. Ale ten zbiór słów to język $L$. Otrzymujemy zatem $L=|(\alpha +\beta {)}^{*}|=|({\alpha }^{*}{\beta }^{*}{)}^{*}|$. Zatem wyrażenia są równoważne.

Rozwiązanie punktu 5

Równość wynika z faktu, że $\mathrm{\forall }\alpha 1\in |\alpha {|}^{*}$.

Rozwiązanie punktu 6

Użyj rozumowania podobnego do tego z rozwiązania punktu 4.

Ćwiczenie 4

Udowodnij, że dla dowolnych wyrażeń regularnych $\alpha$, $\beta$ i $\gamma$ wyrażenia

$\alpha \beta +{\gamma }^{*},(\alpha \beta +\gamma {)}^{*}\text{oraz}\alpha (\beta +\gamma {)}^{*}$

nie są równoważne.

Rozwiązanie

$1\notin |\alpha (\beta +\gamma {)}^{*}|$, natomiast należy do dwóch pozostałych wyrażeń.
$|\alpha \beta \gamma |\subset |(\alpha \beta +\gamma {)}^{*}|$ i $|\alpha \beta \gamma |⊈|\alpha \beta +{\gamma }^{*}|$

Ćwiczenie 5

Sprawdź, czy następujące wyrażenia regularne są równoważne ($\alpha$ oraz $\beta$ są dowolnymi wyrażeniami regularnymi.)

(1) $(\alpha \beta +\alpha {)}^{*}\alpha =\alpha (\beta \alpha +\alpha {)}^{*}$,

(2) $\beta (\alpha \beta +\beta {)}^{*}\alpha =\alpha {\alpha }^{*}\beta (\alpha {\alpha }^{*}\beta {)}^{*}$,

(3) $(\beta {\alpha }^{*}{)}^{*}=\beta (\alpha +\beta {)}^{*}+1$,

Rozwiązanie punktu 1

Każde słowo $w$ opisane wyrażeniem po lewej stronie równości zapisać można jako słowo opisane wyrażeniem $(\alpha \gamma )(\alpha \gamma )...(\alpha \gamma )\alpha$, gdzie $\gamma =\beta$ lub $\gamma =1$ i czynników postaci $(\alpha \gamma )$ może być dowolnie dużo, w zależności od postaci słowa $w$ (w szczególności może nie występować ani jeden; wtedy wyrażenie przyjmie postać $\alpha$). Każde słowo $w$ opisane wyrażeniem stojącym po prawej stronie równości można zapisać jako słowo opisane wyrażeniem $\alpha (\gamma \alpha )...(\gamma \alpha )(\gamma \alpha )$, gdzie $\gamma =\beta$ lub $\gamma =1$ i tak jak w poprzednim przypadku, zależnie od słowa $w$ czynników $(\gamma \alpha )$ może być dowolnie dużo. Usuwając nawiasy widzimy, że dla każdego słowa $w$ wyrażenia te są sobie równe, zatem $(\alpha \beta +\alpha {)}^{*}\alpha =\alpha (\beta \alpha +\alpha {)}^{*}$.

Rozwiązanie punktu 2

Wyrażenia nie są równoważne, gdyż to stojące po lewej stronie równości rozpoczyna się od $\beta$, a to stojące po prawej stronie równości - od $\alpha$.

Rozwiązanie punktu 3

Wyrażenie $(\beta {\alpha }^{*}{)}^{*}$ opisuje słowa postaci $b_1{x}_1{b}_2{x}_2...b_n{x}_n$, gdzie $n\ge 0$, a każde $x_i$ jest postaci $a_1^i...a_{k(i)}^i$, gdzie $k(i)\ge 0$. Słowa $b_i$ opisywane są wyrażeniem $\beta$, każde $x_i$ opisywane jest wyrażeniem ${\alpha }^{*}$, a każde $a_i$ -wyrażeniem $\alpha$. Wyrażenie $\beta (\alpha +\beta {)}^{*}+1$ opisuje natomiast słowa postaci 1 lub $b_1{y}_1{y}_2...y_n$ gdzie $n\ge 0$, $b_i$ opisywane jest wyrażeniem $\beta$, a każde $y_1$ jest słowem opisywanym wyrażeniem $\alpha$ lub $\beta$.

Jeśli słowo jest postaci $b_1{x}_1{b}_2{x}_2...b_n{x}_n$, to widać, że opisane jest także przez wyrażenie stojące po prawej stronie równości, gdyż $x_i=a_1^i{a}_2^i...a_{k(i)}^i$ może być reprezentowane przez słowo złożone z podsłów postaci $y_1^i...y_{k(i)}^i$, przyjmując $y_j^i=a_j^i$, $1\le j\le k(i)$, $k(i)\ge 0$, natomiast każde $b_j$ może być reprezentowane przez słowo $y_j$ przyjmując $y_j=b_j$.

Na odwrót, każde słowo postaci $b_1{y}_1{y}_2...y_n$ można opisać wyrażeniem stojącym po lewej stronie równości, grupując wszystkie $y_i$ występujące obok siebie i opisywane wyrażeniem $\alpha$ i każdą taką grupę reprezentować jako pewne $x_i$, a każde $y_i$ opisywane wyrażeniem $\beta$ reprezentować jako pewne $b_i$.

Ćwiczenie 6

Określ za pomocą wyrażeń regularnych następujące języki:

(1) wszystkie czteroliterowe słowa nad alfabetem $A=\{a,b,c,d\}$,

(2) wszystkie trzyliterowe słowa nad alfabetem $A=\{a,b,c,d\}$, w których występuje dokładnie jedna litera $a$,

(3) wszystkie słowa o dowolnej długości nad alfabetem $A=\{a,b,c,d\}$, w których występuje dokładnie jedna litera $a$,

(4) język poprawnych adresów stron www, jeśli założymy, że poprawny adres strony www składa się ze słowa "$http://www$.", a następnie ciągu liter i cyfr zawierającego przynajmniej jedną kropkę, przy czym ostatnim znakiem tego ciągu nie może być kropka.

(5) ogół sekwencji binarnych, w których liczba zer jest podzielna przez 3,

Rozwiązanie punktu 1

$\alpha =(a+b+c+d)(a+b+c+d)(a+b+c+d)(a+b+c+d)$.

Rozwiązanie punktu 2

$\beta =a(b+c+d)(b+c+d)+(b+c+d)a(b+c+d)+(b+c+d)(b+c+d)a$.

Rozwiązanie punktu 3

$\beta =(b+c+d{)}^{*}a(b+c+d{)}^{*}$.

Rozwiązanie punktu 4

Wyrażenie opisujące zbiór wszystkich takich adresów może mieć postać:

$\gamma =http://www.(a+b+...+z+0+...+9{)}^{+}(.(a+b+...+z+0+...+9{)}^{+}{)}^{+}$

Rozwiązanie punktu 5

$\delta =(1^{*}01^{*}01^{*}01^{*}{)}^{*}$.

Dla uproszczenia, zgodnie z umową przyjętą na wykładzie, jeśli język $L=|\alpha |$ dla pewnego wyrażenia regularnego $\alpha$, to $L$ będziemy zapisywać jako $\alpha$.

Ćwiczenie 7

Niech $L$ będzie językiem określonym przez wyrażenie regularne $a^{*}b{a}^{*}$ nad alfabetem $A=\{a,b\}$ . Określ prawą kongruencję syntaktyczną $P_L^r$ i kongruencję syntaktyczną $P_L$ dla tego języka.

Rozwiązanie

Widać, że dwa słowa będą należały do tej samej klasy abstrakcji relacji $P_L^r$, jeśli będą miały taką samą ilość liter $b$. Zatem $L/P_L^r=\{[1],[b],[bb]\}$, gdzie
$[1]=a^{*}$,
$[b]=a^{*}b{a}^{*}$,
$[bb]=A^{*}b{A}^{*}b{A}^{*}$

Dla języka $L=a^{*}b{a}^{*}$ jest $P_L^r=P_L$.

Ćwiczenie 8

Wykorzystując ciąg relacji zdefiniowanych w twierdzeniu 3.3 w wykładu 4 (patrz twierdzenie 3.3 wykład 4) określ prawą kongruencję syntaktyczną $P_L^r$ dla następujących języków.

(1) $L=(a^2{)}^{*}$

(2) $L=a(a+b{)}^{*}+(a+b{)}^{*}b$

Rozwiązanie punktu 1

${\rho }_1$: $(a^2{)}^{*}$, $a^{*}\setminus (a^2{)}^{*}=(a^2{)}^{*}a$

${\rho }_2={\rho }_1=P_L^r$

Rozwiązanie punktu 2

${\rho }_1$ : $a(a+b{)}^{*}+(a+b{)}^{*}b=a(a+b{)}^{*}a+b(a+b{)}^{*}b+a(a+b{)}^{*}b+a+b$,
$(a+b{)}^{*}\setminus a(a+b{)}^{*}+(a+b{)}^{*}b=b(a+b{)}^{*}a+1$

${\rho }_2$ : $b(a+b{)}^{*}b+b$,
$a(a+b{)}^{*}a+a(a+b{)}^{*}b+a$,
$b(a+b{)}^{*}a$,
$1$,

${\rho }_3={\rho }_2=P_L^r$

Ćwiczenie 9

Zdefiniuj minimalny automat akceptujący następujące języki:

(1) $L=(a^2{)}^{*}$

(2) $L=a(a+b{)}^{*}+(a+b{)}^{*}b$

Rozwiązanie

Zgodnie z wnioskiem lekcja4-w wniosek 3.1 automat minimalny rozpoznający język $L$ ma postać

${{𝒜}}_L=(A^{*}{/}_{P_L^r},f^{*},[1{]}_{P_L^r},T)$

gdzie $T=\{[w{]}_{P_L^r}:w\in L\},$. Korzystając z ćwiczenia 8 (patrz ćwiczenie 8) dostajemy

(1) $S=\{s_0,s_1\}$, gdzie $s_0=(a^2{)}^{*},s_1=(a^2{)}^{*}a$, a działanie automatu określone jest poprzez graf

Rysunek 1

(2) $S=\{s_0,s_1,s_2,s_3\}$, gdzie $s_0=1,s_1=b(a+b{)}^{*}a$,

$s_2=a(a+b{)}^{*}a+a(a+b{)}^{*}b+a,s_3=b(a+b{)}^{*}b+b$,

a działanie automatu określone jest poprzez graf

Rysunek 2

ZADANIA DOMOWE

Ćwiczenie 10

Udowodnij równoważności wyrażeń regularnych ($\alpha$, $\beta$ i $\gamma$ są dowolnymi wyrażeniami regularnymi).

(1) $(\alpha +\beta )+\gamma =\alpha +(\beta +\gamma )$,

(2) $(\alpha \beta )\gamma =\alpha (\beta \gamma )$,

(3) $(\alpha +\beta )\gamma =\alpha \gamma +\beta \gamma$,

(4) $({\alpha }^{*}{)}^{*}={\alpha }^{*}$,

Ćwiczenie 11

Sprawdź, czy następujące wyrażenia regularne są równoważne ($\alpha$ oraz $\beta$ są dowolnymi wyrażeniami regularnymi.)

(1) $(\alpha +\beta {)}^{*}={\alpha }^{*}+{\beta }^{*}$.

(2) $({\alpha }^{*}\beta {)}^{*}{\alpha }^{*}=(\alpha +\beta {)}^{*}$,

(3) $(\alpha +{\beta }^{*}{)}^{*}=({\alpha }^{*}{\beta }^{*}{)}^{*}$,

(4) $\alpha (\alpha \beta +\beta {)}^{*}\alpha =\alpha {\alpha }^{*}\beta (\alpha {\alpha }^{*}\beta {)}^{*}\alpha$,

(5) $\alpha (\alpha \beta +\beta {)}^{*}\alpha =\alpha (\beta \alpha +\alpha {)}^{*}$.

Ćwiczenie 12

Określ za pomocą wyrażeń regularnych następujące języki:

(1) ogół sekwencji binarnych, w których występują co najwyżej trzy zera,

(2) ogół sekwencji binarnych, w których występują co najwyżej dwa zera obok siebie,

(3) ogół sekwencji binarnych, w których liczba zer jest podzielna przez dwa, a liczba jedynek przez 3,

(4) język poprawnych adresów e-mail. Dla uproszczenia przyjmujemy, że poprawny adres e-mailowy składa się z niepustego identyfikatora złożonego z samych liter (maksymalnie z czterech), znaku "małpy", niepustej nazwy serwera złożonej z samych liter (maksymalnie czterech), kropki oraz dwuliterowej nazwy domeny. Alfabet składa się tylko z liter $a$, $b$ i $c$.

Ćwiczenie 13

Wykorzystując ciąg relcji zdefiniowanych w twierdzeniu lekcja4-w-tw? określ prawą kongruencję syntaktyczną $P_L^r$ dla następujących języków.

(1) $L=ab$

(2) $L=(a+b{)}^{*}ab(a+b{)}^{*}$

Ćwiczenie 14

Zdefiniuj minimalny automat akceptujący następujące języki:

(1) $L=ab$

(2) $L=(a+b{)}^{*}ab(a+b{)}^{*}$