Języki, automaty i obliczenia/Ćwiczenia 5: Algorytmy konstrukcji automatu minimalnego

Ćwiczenia 5

Ćwiczenie 1.1

{{{3}}}

Ćwiczenie 1.2

Niech $k\in {\mathbb{\mathbb{N}}}_0$ będzie dowolną, ustaloną liczbą. Wykaż, że automat rozpoznający język

$L=\{a^n{b}^n:0\le n\le k\}$

ma co najmniej $2k+2$ stany.

Rozwiązanie

Automat

RYSUNEK ja-lekcja5-c-rys2

akcepuje język $L$ i jest automatem minimalnym (jego minimalizacja daje automat izomorficzny, wszystkie klasy są jednoelementowe).

}}

Ćwiczenie 1.3

{{{3}}}

Ćwiczenie 1.4

{{{3}}}

Ćwiczenie 1.5

Wykorzystując algorytm stabilizujących się relacji wyznacz automaty minimalne dla automatów z rysunków Uzupelnic ja-lekcja5-c-rys3| oraz Uzupelnic ja-lekcja5-c-rys4|.

Ćwiczenie [Uzupelnij]

Niech $L=A^{*}a{A}^{*}b{A}^{*}$, gdzie $A=\{a,b\}$. Zastosuj algorytm wykorzystujący pochodną Brzozowskiego do obliczenia automatu minimalnego dla tego języka.

ROZWIĄZANIE. Obliczamy zgodnie z algorytmem kolejne pochodne zaczynając od języka $L$. Dla uproszczenia oznaczmy $X=L\cup A^{*}b{A}^{*}=A^{*}a{A}^{*}b{A}^{*}\cup A^{*}b{A}^{*}$, $Y=X\cup A^{*}=A^{*}$.

Parser nie mógł rozpoznać (nieznana funkcja „\aligneda”): {\displaystyle \aligneda^{-1}L & = & a^{-1}(A^*aA^*bA^*) = A^*aA^*bA^* \cup A^*bA^* = X\\ b^{-1}L & = & b^{-1}(A^*aA^*bA^*) = A^*aA^*bA^* = L\\ a^{-1}X & = & a^{-1}(A^*aA^*bA^*) \cup a^{-1}A^*bA^* = X \cup A^*bA^* = X\\ b^{-1}X & = & b^{-1}(A^*aA^*bA^*) \cup b^{-1}A^*bA^* = L \cup A^*bA^* \cup A^* = A^* = Y\\ a^{-1}Y & = & a^{-1}A^* = A^* = Y\\ b^{-1}Y & = & b^{-1}A^* = A^* = Y \endaligned}

Automat minimalny ma więc trzy stany, odpowiadające odpowiednio językom $L=A^{*}a{A}^{*}b{A}^{*}$, $X=A^{*}a{A}^{*}b{A}^{*}\cup A^{*}b{A}^{*}$ orazy $Y=A^{*}$. Stanem początkowym jest oczywiście stan $L$, natomiast stanem końcowym - stan $Y$ (dlaczego?). Automat minimalny przedstawiony jest na rysunku Uzupelnic ja-lekcja5-c-rys5|.

RYSUNEK ja-lekcja5-c-rys5

Poniżej znajduje się opis jeszcze jednego algorytmu minimalizacji -- algorytmu Hopcrofta. Jest on nieco bardziej skomplikowany niż trzy podane dotychczas algorytmy, ale posiada lepszą złożoność niż algorytm obliczania stanów rozróżnialnych czy też algorytm wyznaczania ciągu relacji stabilizujących. Przeanalizuj opis algorytmu i jego zapis, a następnie rozwiąż zadanie Uzupelnic cw_hop|.

Algorytm Hopcrofta

Niech ${𝒜}=(S,A,f,s_0,T)$ będzie automatem, a $Q\subset S$ podzbiorem. Dowolny podzbiór $R\subset S$ i dowolna litera $a\in A$ wyznaczają na zbiorze $Q$ relację równoważności o dwóch klasach abstrakcji:

$Q_1=\{s\in Q:f(s,a)\in R\};Q_2=\{s\in Q:f(s,a)\in ̸R\},$

przy czym jeśli jeden ze zbiorów $Q_1,Q_2$ jest pusty, to relacja ta posiada tylko jedną klasę abstrakcji. Wprost z definicji zbiory $Q_1$ i $Q_2$ tworzą podział zbioru $Q$ (tzn. $Q=Q_1\cup Q_2,Q_1\cap Q_2=\mathrm{\varnothing }$).Oznaczmy omawianą relację przez ${\rho }_R^a$.

W algorytmie zmienna $P$ oznacza podział zbioru stanów $S$, a ${ℒ}$ - listę par $(Y,a)$, które będą wykorzystane do definiowania kolejnych relacji ${\rho }_Y^a$.

{{MinHopcroft} - algorytm Hopcrofta minimalizacji automatu} [1] Wejście: ${𝒜}=(S,A,f,s_0,T)$ -- automat taki, że $L=L({𝒜})$

Wyjście: $P$ -- podział zbioru $S$ przez prawą kongruencję automatową

$P\leftarrow \{T,S\mathrm{\setminus }T\}$; Parser nie mógł rozpoznać (nieznana funkcja „\trianglerightP”): {\displaystyle \trianglerightP} jest zbiorem rozłącznych podzbiorów $S$

{ $|T|<|S\mathrm{\setminus }T|$}

{each $a\in A$} włóż$({ℒ},(T,a))$;

{each $a\in A$} włóż$({ℒ},(S\mathrm{\setminus }T,a))$;

{ ${ℒ}\ne \mathrm{\varnothing }$ }

$(Y,a)\leftarrow$ zdejmij $({ℒ})$;

Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle \mathcal{X} \leftarrow \{X \in P:\ |X \slash \rho^a_Y| = 2\}} ;

{each $X\in {𝒳}$} {each $b\in A$}

Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle \{X_1, X_2\} \leftarrow X \slash \rho^a_Y} ; Parser nie mógł rozpoznać (nieznana funkcja „\trianglerightX”): {\displaystyle \trianglerightX \slash \rho^a_Y} zawiera dwie klasy abstrakcji

$P\leftarrow (P\mathrm{\setminus }X)\cup X_1\cup X_2$;

{$(X,b)\in {ℒ}$}

${ℒ}\leftarrow {ℒ}\mathrm{\setminus }(X,b)$; $▹$ zdejmij z ${ℒ}$ dokładnie parę $(X,b)$

włóż$({ℒ},(X_1,b))$;

włóż$({ℒ},(X_2,b))$;

{ $|X_1|<|X_2|$} włóż$({ℒ},(X_1,b))$;

włóż$({ℒ},(X_2,b))$;

$P$;

Funkcja zdejmij(${ℒ}$) pobiera z listy ${ℒ}$ dowolny element i zwraca go jako swoją wartość. Procedura włóż(${ℒ},X$) dodaje do listy ${ℒ}$ element $X$.

Aby zdefiniować funkcję przejść automatu minimalnego, jego zbiór stanów końcowych oraz stan początkowy, należy postąpić identycznie jak w algorytmie wyznaczania ciągu stabilizujących się relacji. Jedyna różnica polega na tym, że w miejsce relacji otrzymaliśmy podział zbioru $S$ na klasy abstrakcji zadane przez poszukiwaną relację. Oczywiście klasy abstrakcji wyznaczają jednoznacznie relację równoważności i na odwrót -- relacja równoważności wyznacza jednoznacznie podział zbioru na klasy równoważności, zatem forma opisu relacji przez klasy abstrakcji nie stanowi dla nas żadnego problemu.

Przy właściwej reprezentacji wszystkich używanych struktur, algorytm {MinHopcroft} działa w czasie $|A|n\log n$, gdzie $n$ jest liczbą stanów automatu, a $|A|$ rozmiarem jego alfabetu wejściowego. Wyjściem algorytmu jest podział $P$ zbioru stanów. Każdy element zbioru $P$ reprezentuje jeden stan automatu minimalnego.

Ćwiczenie [Uzupelnij]

Zastosuj algorytm Hopcrofta do zminimalizowania automatu z rysunku Uzupelnic ja-lekcja5-c-rys3| (patrz zadanie Uzupelnic cw_first|).

ROZWIĄZANIE. Na początku podział $P$ dzieli $S$ na $P_1=\{s_1,s_2\}$ i $P_2=\{s_3,s_4,s_5,s_6\}$. Ponieważ $|P_1|<|P_2|$ do pustej listy dodajemy $(\{s_1,s_2\},a)$ oraz $(\{s_1,s_2\},b)$.

Przechodzimy do pętli while (linia 5.). Zdejmujemy z ${ℒ}$ element $(Y,a)=(\{s_1,s_2\},a)$. Dla każdego elementu $X$ podziału $P$ sprawdzamy, czy ${\rho }_Y^a$ podzieli $X$.

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned\{s_1,s_2\} \slash \rho_{\{s_1,s_2\}}^a & = & \{s_1,s_2\}, \\ \{s_2,s_3,s_4,s_5,s_6\} \slash \rho_{\{s_1,s_2\}}^a & = & \{s_3,s_4,s_5,s_6\}. \\ \endaligned}

Zdejmujemy z ${ℒ}$ kolejny element, $(Y,a)=(\{s_1,s_2\},b)$ . Obliczamy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned\{s_1,s_2\} \slash \rho_{\{s_1,s_2\}}^b & = & \{s_1,s_2\} \\ \{s_2,s_3,s_4,s_5,s_6\} \slash \rho_{\{s_1,s_2\}}^b & = & \{s_3,s_4\},\{s_5,s_6\} \\ \endaligned}

Relacja ${\rho }_{\{s_1,s_2\}}^b$ podzieliła zbiór $\{s_3,s_4,s_5,s_6\}$.
( $f(s_3,b),f(s_4,b)\in \{s_1,s_2\}$, $f(s_5,b),f(s_6,b)\in ̸\{s_1,s_2\}$. )
$P=\{s_1,s_2\},\{s_3,s_4\},\{s_5,s_6\}$. Usuwamy $(\{s_1,s_2\},b)$ z ${ℒ}$. Ponieważ na liście ${ℒ}$ nie było ani elementu $(\{s_3,s_4,s_5,s_6\},a)$, ani $(\{s_3,s_4,s_5,s_6\},b)$, do listy dodajemy elementy $(\{s_3,s_4\},a)$, $(\{s_3,s_4\},b)$, $(\{s_5,s_6\},a)$ oraz $(\{s_5,s_6\},b)$.

Powracamy do początku pętli. Zdejmujemy z ${ℒ}$ element $(Y,a)=(\{s_3,s_4\},a)$. Obliczamy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned\{s_1,s_2\} \slash \rho_{\{s_3,s_4\}}^a & = & \{s_1,s_2\} \\ \{s_3,s_4\} \slash \rho_{\{s_3,s_4\}}^a & = & \{s_3,s_4\} \\ \{s_5,s_6\} \slash \rho_{\{s_3,s_4\}}^a & = & \{s_5,s_6\} \\ \endaligned}

${\rho }_{\{s_3,s_4\}}^a$ nie dzieli żadnego z elementów podziału $P$. Zdejmujemy więc z ${ℒ}$ kolejny element, $(Y,a)=(\{s_3,s_4\},b)$.
Sprawdź, że żadna z relacji: ${\rho }_{\{s_3,s_4\}}^b$, ${\rho }_{\{s_5,s_6\}}^a$, ${\rho }_{\{s_5,s_6\}}^b$ nie utworzy nowego podziału.

$(\{s_5,s_6\},b)$ jest ostatnim elementem listy i algorytm kończy działanie. Ostateczny podział zbioru $S$ ma postać: $\{s_1,s_2\},\{s_3,s_4\},\{s_5,s_6\}$. Automat minimalny ma więc 3 stany, odpowiadające elementom podziału. Stanem początkowym jest stan $\{s_3,s_4\}$, a końcowym -- stan $\{s_1,s_2\}$.

Otrzymaliśmy ten sam automat minimalny, co w zadaniu Uzupelnic cw_first|.

ZADANIA DOMOWE

Ćwiczenie [Uzupelnij]

Zminimalizuj przedstawione poniżej automaty:

1. stosując algorytm wyznaczający stany rozróżnialne,

1. stosując algorytm stabilizujących się relacji,

1. stosując algorytm Hopcrofta.

RYSUNEK ja-lekcja5-c-rys6

RYSUNEK ja-lekcja5-c-rys7

Ćwiczenie [Uzupelnij]

Niech $L=A^{*}a{A}^2$, gdzie $A=\{a,b\}$. Zastosuj algorytm wykorzystujący pochodną Brzozowskiego do obliczenia automatu minimalnego dla tego języka.