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

{theor}{TWIERDZENIE}[section] {rem}{UWAGA}[section] {corol}{WNIOSEK}[section] {fact}{FAKT}[section] {ex}{PRZYKŁAD}[section] {defin}{DEFINICJA}[section] {lem}{LEMAT}[section] {cw}{ĆWICZENIE}[section]

{prf}{DOWÓD}

{Algorytmy konstrukcji automatu minimalnego}

ĆWICZENIA 5

Ćwiczenie [Uzupelnij]

Ile co najmniej stanów ma automat akceptujący dokładnie jedno słowo $w$ o długości $n$?

ROZWIĄZANIE. Minimalny automat akceptujący słowo $a_1...a_n$ ma $n+2$ stany.

RYSUNEK ja-lekcja5-c-rys1

Ćwiczenie [Uzupelnij]

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 [Uzupelnij]

Niech Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle \mathcal{B}=(S \slash \equiv, A, f', [s_0], T)} będzie automatem minimalnym dla automatu ${𝒜}=(S,A,f,s_0,T)$. Czy zbiór stanów Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle S \slash \equiv} automatu minimalnego obliczonego za pomocą algorytmu wyznaczania stanów rozróżnialnych, zależy od:

1. wyboru w ${𝒜}$ stanu początkowego $s_0$,

1. wyboru w ${𝒜}$ zbioru stanów końcowych $T$?

ROZWIĄZANIE punktu 1. Nie. Wynika to bezpośrednio z analizy algorytmu. Relacja $\equiv$ nie rozróżnia stanów ze względu na stan początkowy. Stan początkowy nie jest w żaden sposób wyróżniony w algorytmie podczas konstrukcji zbioru Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle S \slash \equiv } .

ROZWIĄZNIE punktu 2. Tak, gdyż postać relacji $\equiv$ zależy od tego jakie pary stanów są zaznaczone jako stany rozróżnialne, a w liniach 3. i 4. algorytmu, początkowe wyznaczenie stanów rozróżnialnych jest zależne od postaci zbioru $T$.

Ćwiczenie [Uzupelnij]

Zastosuj algorytm wyznaczający stany rozróżnialne do zminimalizowania następujących automatów:

1. RYSUNEK ja-lekcja5-c-rys3

1. RYSUNEK ja-lekcja5-c-rys4

ROZWIĄZANIE punktu 1. Po wypełnieniu tabelki stwierdzamy, że $s_1\equiv s_2$, $s_3\equiv s_4$ oraz $s_5\equiv s_6$, zatem automat minimalny ma 3 stany: $[s_1,s_2]$, $[s_3,s_4]$ oraz $[s_5,s_6]$.

WSKAZÓWKA do punktu 2. Zauważ, że stany $s_1$, $s_3$, $s_5$, $s_6$ i $s_7$ są równoważne. Przed rozpoczęciem algorytmu "sklej" je w jeden stan tak, aby uprościć automat, który będziesz minimalizował. W ten sposób zamiast minimalizować automat 10-stanowy, będziesz minimalizował automat o 6 stanach.

ROZWIĄZANIE punktu 2. Sklejmy stany $s_1,s_3,s_5,s_6,s_7$ w jeden stan (od razu widać, że są równoważne) i powstały w ten sposób stan oznaczmy jako $s_0$. Po wypełnieniu tabelki okazuje się, że wszystkie jej pola są wypełnione X-ami. Zatem każde dwa spośród stanów $s_0,s_2,s_4,s_8,s_9,s_{10}$ są rozróżnialne. Automat minimalny posiada więc 6 stanów.

Ćwiczenie [Uzupelnij]

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.