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

From Studia Informatyczne

Ć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^*| \not = |\beta| \cdot |\alpha|^*.

Rozwiązanie punktu 4

Niech L będzie językiem złożonym ze słów postaci y=y_1y_2...y_n, n \geq 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_1y_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^1y_b^1)...(y_a^ky_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^1y_b^1)...(y_a^ky_b^k) jest więc opisywany wyrażeniem (\alpha^* \beta^*)^*, przy czym wyrażenie w nawiasie "odpowiada" pojedynczej sekwencji y_a^jy_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 \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| \nsubseteq |\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_1x_1b_2x_2...b_nx_n, gdzie n \geq 0, a każde {x_i} jest postaci a^i_1...a^i_{k(i)}, gdzie k(i) \geq 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_1y_1y_2...y_n gdzie n \geq 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_1x_1b_2x_2...b_nx_n, to widać, że opisane jest także przez wyrażenie stojące po prawej stronie równości, gdyż x_i=a^i_1a^i_2...a^i_{k(i)} może być reprezentowane przez słowo złożone z podsłów postaci y^i_1...y^i_{k(i)}, przyjmując y^i_j=a^i_j, 1 \leq j \leq k(i), k(i) \geq 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_1y_1y_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:\slash \slash 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^*ba^* 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 \slash P_L^r = \{[1],[b],[bb]\}, gdzie
[1]=a^*,
[b]=a^*ba^*,
[bb]=A^*bA^*bA^*

Dla języka L=a^*ba^* 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ć

\mathcal{A}_{L}=\left( A^{*}/_{P^{r}_{L}},f^{*},[1]_{P^{r}_{L}},T\right),

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

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

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

<flash>file=ja-lekcja04-c-rys2.swf|width=250|height=250</flash>

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)^*