Analiza leksykalna. Języki regularne i maszyny o skończonych stanach
przez sumę znaków alfabetu symboli i znaków operacji oraz nawiasów w haśle r.Podstawa. Automaty dla wyrażeń o długości 1: i pokazano na poniższym rysunku.
Ryż. 5.1.
Należy zauważyć, że dla każdego z tych trzech automatów zbiór stanów końcowych składa się z jednego stanu.
Krok indukcyjny. Załóżmy teraz, że dla każdego wyrażenia regularnego o długości = 1 słowo w można podzielić na k podsłów: w=w 1 w 2 ... w k i to wszystko. Dla każdego i= 1,... ,k słowo w i przekłada q 0 1 na q f 1 . Wtedy dla słowa w na schemacie M istnieje ścieżka
Stąd, . I odwrotnie, jeśli jakieś słowo tłumaczy q 0 na q f , to albo istnieje, albo jest niesione ścieżką, która po przejściu od q 0 do q 0 1, a następnie kilkukrotnym przejściu ścieżką od q 0 1 do q f 1 i powrocie od q f 1 do q 0 1 przez -przejście, ostatecznie od q f 1 przez -przejście kończy się na q f . Dlatego takie słowo.
Z twierdzeń 4.2 i 5.1 otrzymujemy bezpośrednio
Wniosek 5.1. Dla każdego wyrażenia regularnego można skutecznie zbudować deterministyczną maszynę o skończonych stanach, która rozpoznaje język reprezentowany przez to wyrażenie.
To stwierdzenie jest jednym z przykładów twierdzeń syntezy: na podstawie opisu zadania (języka jako wyrażenia regularnego) skutecznie konstruuje się program (DFA), który je wykonuje. Prawdziwe jest również odwrotne zjawisko – twierdzenie analizy.
Twierdzenie 5.2. Dla każdej deterministycznej (lub niedeterministycznej) maszyny skończonej możliwe jest skonstruowanie wyrażenia regularnego reprezentującego język rozpoznawany przez tę maszynę.
Dowód tego twierdzenia jest dość techniczny i wykracza poza zakres naszego kursu.
Możemy zatem stwierdzić, że klasa języków automatów skończonych pokrywa się z klasą języków regularnych. Odtąd będziemy ją nazywać po prostu klasą języków automatów.
Automat M r, który jest skonstruowany w dowodzie Twierdzenia 5.1
Podstawowe definicje Wyrażenia regularne w alfabecie Σ i oznaczane przez nie zbiory regularne definiuje się rekurencyjnie w następujący sposób: 1) – wyrażenie regularne oznaczające zbiór regularny; 2) e – wyrażenie regularne oznaczające zbiór regularny (e); 3) jeśli a Σ, to a jest wyrażeniem regularnym oznaczającym zbiór regularny (a); 4) jeśli p i q są wyrażeniami regularnymi oznaczającymi zbiory regularne P i Q, to a) (p+q) jest wyrażeniem regularnym oznaczającym P Q; b) pq – wyrażenie regularne oznaczające PQ; c) p* – wyrażenie regularne oznaczające P*; 5) nic innego nie jest wyrażeniem regularnym.
Podstawowe definicje Priorytetyzacja: * (iteracja) – najwyższy priorytet; powiązanie; + (zjednoczenie). Zatem 0 + 10* = (0 + (1 (0*))). Przykłady: 1. 01 oznacza (01); 2. 0* – (0*); 3. (0+1)* – (0, 1)*; 4. (0+1)* 011 – oznacza zbiór wszystkich łańcuchów składających się z 0 i 1 i kończących się łańcuchem 011; 5. (a+b) (a+b+0+1)* oznacza zbiór wszystkich łańcuchów (0, 1, a, b)* zaczynających się od a lub b.
Podstawowe definicje lematu: 1) α + β = β + α 2) * = e 3) α + (β + γ) = (α + β) + γ 4) α(βγ) = (αβ)γ 5) α( β + γ) = αβ + αγ 6) (α + β)γ = αγ + βγ 7) αe = eα = α 8) α = 9) α+α* = α* 10) (α*)* = α* 11) α+α = α 12) α+ = α
Związek pomiędzy RT i RM RM to języki generowane przez RT. Na przykład: x = a+b, y = c+d, x X = (a, b), y Y = (c, d), x + y X Y = (a, b, c, d). Konkatenacja: xy XY = (ac, ad, bc, bd). k(u+o)t (k)(u, o)(t) = (wieloryb, kot) lub lematy nr 5 i nr 6 k(u+o)t = wieloryb + kot (wieloryb, kot) . Iteracja: x = a, x* X* = (e, a, aaa, …), tj. x* = e + xxx + …
Połączenie pomiędzy RP i RM Iteracja konkatenacji i połączenia: (xy)* = e + xyxyxy + … (x + y)* = e + (x + y)(x + y) + … = = e + xx + xy + yx + yy + xxx + … Przykład: 0 + 1(0+1)* (0) ((1) (0, 1)*) = (0, 1, 10, 11, 100, 101, 110, 111… ). Suma jest przemienna: x + y = y + x Konkatenacja nie jest: xy ≠ yx
Komunikacja pomiędzy RM i RM Przykłady priorytetów: x + yz (x, yz), (x + y)z (xz, yz), x + y* (e, x, y, yyy, yyyy, ...), (x + y)* (e, x, y, xx, xy, yx, yy, xxx, …), (xy)* (e, xyxy, …), xy* (x, xyy, xyyy, …). Nowe lematy: a* + e = a*; (a + e)* = a*; a*a* = a*; e* = mi; itp.
Regularne układy równań Równanie ze współczynnikami regularnymi X = a. X + b ma rozwiązanie (najmniejszy punkt stały) a*b: aa*b + b = (aa* + e)b = a*b Układ równań o regularnych współczynnikach: X 1 = α 10 + α 11 X 1 + α 12 X 2 + … + α 1 rz. Xn X 2 = α 20 + α 21 X 1 + α 22 X 2 + … + α 2 n. Xn…………………………. . Xn = αn 0 + αn 1 X 1 + αn 2 X 2 + … + αnn. Xn Niewiadome – Δ = (X 1, X 2, …, Xn).
Regularne układy równań Algorytm rozwiązania (metoda Gaussa): Krok 1. Ustaw i = 1. Krok 2. Jeśli i = n przejdź do kroku 4. W przeciwnym razie równania dla Xi zapisz w postaci Xi = αXi + β (β = β 0 + βi +1 Xi+1 + … + βn.Xn). Następnie po prawej stronie równań Xi+1, ..., Xn zastępujemy Xi wyrażeniem regularnym α*β. Krok 3. Zwiększ i o 1 i wróć do kroku 2. Krok 4. Zapisz równanie dla Xn jako Xn = αXn + β. Przejdź do kroku 5 (przy i = n). Krok 5. Równanie Xi to Xi = αXi + β. Na wyjściu napisz Xi = α*β, w równaniach dla Xi– 1, …, X 1, podstawiając α*β zamiast Xi. Krok 6. Jeśli i = 1, zatrzymaj się, w przeciwnym razie zmniejsz i o 1 i wróć do kroku 5.
Transformacja DFA na RT Dla DFA M = (Q, Σ, δ, q 0, F) tworzymy układ o regularnych współczynnikach gdzie Δ = Q: 1. zbiór αij: = ; 2. jeśli δ(Xi, a) = Xj, a Σ, to αij: = αij + a; 3. jeśli Xi F lub δ(Xi,) = HALT, to αi 0: = e. Po rozwiązaniu żądana wartość PV będzie wynosić X 1 = q 0.
Konwersja DFA na RV Przykład: dla liczby stałoprzecinkowej otrzymujemy układ q 0 = + q 0 + sq 1 + pq 2 + dq 3 + q 4 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = mi + q 0 + q 1 + q 2 + q 3 + dq 4 Tutaj: s – znak liczby, s = „+” + „–”; p – przecinek dziesiętny, p = „.”; d – liczby, d = „0” + „1” + … + „9”.
Konwersja rozwiązania DFA na RT: q 0 = *(sq 1 + pq 2 + dq 3 + q 4 +) = sq 1 + pq 2 + dq 3 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 = pq 2 + dq 3, q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4, q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = dq 3 + pq 4 + e, q 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4 + e. Z trzeciego równania: q 3 = dq 3 + pq 4 + e = d*(pq 4 + e). Z czwartego równania: q 4 = dq 4 + e = d*.
Konwersja DFA na RT Skok odwrotny: q 3 = d*(pq 4 + e) = d*(pd* + e), q 2 = dq 4 = dd*, q 1 = pq 2 + dq 3 = pdd * + dd *(pd* + e), q 0 = sq 1 + pq 2 + dq 3 = s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Zatem ten DFA odpowiada RT s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Uprośćmy: s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e) = = spdd* + sdd*(pd* + e) + pdd* + dd*(pd* + e) = (s + e)(pdd* + dd*(pd* + e)) Aby uzyskać krótszą notację, możesz użyć iteracji dodatniej aa* = a*a = a+: (s + e)(pdd* + dd* (pd* + e)) = (s + e)(pd+ + d+pd* + d+)
Konwersja DFA do RT Mapowanie wykresu funkcji przejścia DFA na podstawowe operacje za pomocą wyrażeń regularnych: q 0 a b a q 1 q 2 q 1 q 0 a+b a b ab q 2 a*
Konwersja DFA na RT Bardziej złożone kombinacje operacji: q 0 a q 1 b b b q 0 a q 2 q 1 (a + e)b c b q 0 q 2 ab(cab)* q 0 (a + b)* q 0 a q 1 aa* = a+ q 0 a q 1 a b a a (ab)+ q 2 b q 1 do e + (a + b)c*
Konwersja DFA na RT Dla RT (s + e)(pd+ + d+(pd* + e)): q 0 p q 2 d s p q 1 d d q 3 d p q 4 d q 5 d
Programowanie RV Wyrażenia regularne: Wbudowane w wiele języków programowania (PHP, Java. Script, ...); Zaimplementowane jako komponenty wtyczek (np. klasa Regex dla platformy .NET). Różnice w formach zapisu: x? = x + e x(1, 3) = x + xxx itd.
Programowanie Konstrukcje RT klasy Regex (System. Tekst. Regularne. Wyrażenia): Symbol Interpretacja sekwencji ucieczki b Ujęty w nawiasy kwadratowe odpowiada symbolowi „←” (u 0008) t, r, n, a, f, v Tab (u 0009), powrót karetki (u 000 D), nowa linia (u 000 A) itp. X Znak kontrolny (np. c. C to Ctrl+C, u 0003) e Escape (u 001 B) ooo Znak ASCII w formacie ósemkowym xhh Znak ASCII w formacie szesnastkowym uhhhh Znak Unicode Poniższy znak nie jest specjalnym znakiem RT. Symbol ten musi być użyty do ucieczki wszystkich znaków specjalnych.Przykład (przykład pokazuje wzorzec i ciąg wyszukiwania, znalezione dopasowania są podkreślone w ciągu): @"rnw+" – "rn. Tutaj są dwie linie."
Programowanie RV Podzbiory symboli. Dowolny znak z wyjątkiem końca linii (n) Dowolny znak ze zbioru [^xxx] Dowolny znak z wyjątkiem znaków ze zbioru Dowolny znak z zakresu ] Odejmowanie jednego zbioru lub zakresu od innego p(nazwa) Dowolny znak określony przez Unicode kategoria nazwana nazwa P (nazwa) Dowolny znak inny niż określony przez nazwę kategorii Unicode w Zestaw znaków używany przy określaniu identyfikatorów W Zestaw znaków nieużywany przy określaniu identyfikatorów s Spacje S Wszystko z wyjątkiem spacji d Liczby D Niecyfry Przykłady : @”. +” – „rn. Są dwie linie”; @"+" – "0 xabcfx"; @"[^fx]+" – "0 xabcfx"; @"+" – "0 xabcfx"; @"[^a-f]+" – "0 xabcfx"; @"]+" – "0 xabcfx"; @"p(Lu)" – "Światła miasta"; // Lu – wielkie litery @"P(Lu)" – "Miasto"; @"p(jest cyrylicą)" – "ha. OS"; //Jest. Cyrylica – litery rosyjskie
Programowanie PB Anchor ^, A Na początku linii $, Z Na końcu linii lub przed znakiem „n” na końcu linii z Na końcu linii G Miejsce, w którym kończy się poprzednie dopasowanie b Granica słowa B Dowolna pozycja poza granicą słowa. Przykłady: @ „G(d)” – „(1)(3)(5)(9)”; // trzy dopasowania (1), (2) i (3) @"bnS*ionb" – "darowizna narodu"; @"Bendw*b" – "koniec wysyła trwałego pożyczkodawcę".
Programowanie operacji RT (kwantyfikatory) *, *? Iteracja +, +? Pozytywna iteracja? ,? ? Zero czy jedno dopasowanie (n), (n)? Dokładnie n dopasowań (n, ), (n, )? Co najmniej n dopasowań (n, m), (n, m)? Od n do m dopasowań Przykłady (pierwsze kwantyfikatory są zachłanne, szukają jak największej liczby elementów, drugie są leniwe, szukają jak najmniejszej liczby elementów): @"d(3, )" – "888 -5555 "; @"^d(3)" – "913 -913"; @"-d(3)$" – "913 -913"; @"5+? 5" – "888 -5555"; // trzy dopasowania - 55, 55 i 55 @"5+5" - "888 -5555".
Programowanie RV Grupowanie () Grupa, która automatycznie otrzymuje numer (? :) Nie zapisuj grupy (?) lub (? "nazwa") W przypadku znalezienia dopasowania tworzona jest nazwana grupa (?) lub Usuń wcześniej zdefiniowaną grupy i (? "nazwa - nazwa") zapisanie w nowej grupie podciągu pomiędzy wcześniej zdefiniowaną grupą a nową grupą (? imnsx:) Włącza lub wyłącza dowolną z pięciu (? –imnsx:) możliwych opcji w grupie: i – wielkość liter nie jest uwzględniana; s – jedna linia (wtedy „.” jest dowolnym znakiem); m – tryb wielowierszowy („^”, „$” – początek i koniec każdej linii); n – nie przechwytuj nienazwanych grup; x – wyklucz ze wzorca spacje bez ucieczki i dołącz komentarze po znaku liczby (#) (? =) Pozytywna instrukcja lookahead o zerowej długości
Programowanie RT (? !) Ujemna instrukcja lookahead o zerowej długości (?) Bezzwrotna (chciwa) część wyrażenia Przykłady: @"(an)+" – "kroniki bananów"; @"an+" – "kroniki bananów"; // porównaj, trzy dopasowania - an, an i ann @"(? i: an)+" - "ba. NAnas annals"; @"+(? =d)" – "abc xyz 12 555 w"; @”(?
Src="https://site/presentation/-112203859_437213351/image-24.jpg" alt="RV Programowanie Linki numer Link do grupy k Link do nazwanej grupy Przykłady: @"> Программирование РВ Ссылки число Ссылка на группу k Ссылка на именованную группу Примеры: @"(w)1" – "deep"; @"(? w)k " – "deep". Конструкции изменения | Альтернатива (соответствует операции объединения) (? (выражение)да|нет) Сопоставляется с частью «да» , если выражение соответствует; в противном случае сопоставляется с необязательной частью «нет» (? (имя)да|нет), Сопоставляется с частью «да» , если названное имя (? (число)да|нет) захвата имеет соответствие; в противном случае сопоставляется с необязательной частью «нет» Пример: @"th(e|is|at)" – "this is the day";!}
Programowanie RV Podstawienia $number Zastępuje część łańcucha odpowiadającą grupie podanym numerem $(nazwa) Zastępuje część ciągu odpowiadającą grupie o określonej nazwie $$ Zastępuje $ $& Zastępuje kopią pełnego dopasowanie $` Zastępuje tekst wejściowego ciągu znaków do momentu dopasowania $" Zastępuje tekst wierszy wejściowych po dopasowaniu $+ Zastępuje ostatnio przechwyconą grupę $_ Zastępuje całą linię Komentarze (? #) Komentarz wbudowany # Komentarz do końca wiersza
Programowanie RT Wyniki wyrażenia regularnego: Regex Matches() Match. Kolekcja Match Groups() Grupa. Przechwytywanie grupy kolekcji(). Kolekcja przechwytuje()
Przykład programowania RV w C++ CLI (aplikacja konsolowa Visual C++/CLR/CLR): int main() ( Regex ^r = gcnew Regex(L"((\d)+)+"); Match ^m = r-> Match (L"123 456"); int dopasowanie. Liczba = 0; while (m->Success) ( Konsola: : Zapisz. Linia(L"Dopasowanie (0)", ++dopasowanie. Liczba); for (int i = 1; i Groups->Count; i++) ( Grupa ^g = m->Grupy[i]; Konsola: : Zapis. Linia(L" Grupa (0) = "(1)"", i, g-> Wartość ); for (int j = 0; j Przechwytuje->Count; j++) ( Przechwytywanie ^c = g->Przechwytywanie[j]; Konsola: : Zapis. Linia(L" Przechwytywanie (0) = "(1)" , pozycja = (2), długość = (3)", j, c, c->Indeks, c->Długość); ) ) m = m->Następne dopasowanie(); ) return 0; ) System: : Tekst : : Regularne. Wyrażenia
Umożliwienie akcji i wyszukiwanie błędów Ograniczanie liczby cyfr znaczących w liczbie: (s + e)(pd+ + d+(pd* + e)) s = +|p = . d = re s + e = s? = (+|-)? pd* + e = (pd*)? = (.d*)? @"(+|-)? (. d+|d+(. d*)?)" lub @"^(+|-)? (. d+|d+(. d*)?)$" Regex r = nowy Regex (@"^(+|-)? (. (? "cyfra"d)+|(? "cyfra"d)+(. (? "cyfra"d)*)?)$"); Dopasuj m = r. Dopasuj("+1. 23456789"); if (m. Sukces) ( Grupa g = m. Grupy["cyfra"]; if (g. Przechwytywania. Liczba
Włączanie akcji i wyszukiwanie błędów Określenie miejsca błędu: Regex r = nowy Regex(@"(+|-)? (. (? "cyfra"d)+|(? "cyfra"d)+(. (? "cyfra" D )*)?)"); ciąg str = "+1. 2345!678"; Dopasuj m = r. Dopasuj(str); if (m. Sukces) ( Grupa g = m. Grupy["cyfra"]; if (g. Przechwytywania. Liczba 0) Konsola. Zapis. Linia("Błąd na pozycji 1: nieoczekiwany znak "(0)"", str ); else if (m. Długość
Umożliwienie akcji i wyszukiwanie błędów. Ustalenie miejsca wystąpienia błędu: 1. pierwsza pozycja łańcucha wejściowego (1), jeżeli pierwsze dopasowanie nie rozpoczyna się od pozycji Indeks = 0; 2. pozycja następująca po ostatnim dopasowaniu (długość dopasowania + 1), jeżeli nie odpowiada ona ostatniej pozycji łańcucha wejściowego; 3. pozycja pierwszej przerwy pomiędzy dopasowaniami (dopasowanie[i]. Indeks + dopasowanie[i]. Długość + 1), jeśli znak następujący po poprzednim dopasowaniu nie jest pierwszym znakiem kolejnego dopasowania.
Indeks) przerwa; indeks = m[i]. Indeks + m[i]. Długość; ) Konsola. Pisać. Linia("Błąd w pozycji (0) "(1)"", indeks + 1, str); ) "abc. xyz. pqr” – poprawnie; "+abc. xyz. pqr” – błąd na pozycji 1 („+”); "ABC. xyz. pqr! – błąd w pozycji 12 („!”); "ABC. xyz!. pqr” – błąd w pozycji 8 („!”).
Włączanie akcji i wyszukiwanie błędów Ale! "ABC. xyz. +pqr” – błąd na pozycji 8 („.”). Nowa opcja szablonu: @"w+(. w+)*(. (? !$))? " Walidacja: "abc. xyz. +pqr” – błąd na pozycji 9 („+”); "ABC. xyz. pqr. „ – błąd w pozycji 12 („”.”).
Zrównoważone definicje: „(? „x”)” dodaje jeden element do kolekcji o nazwie „x”; „(? „-x”)” usuwa jeden element ze zbioru „x”; „(? (x)(? !))” sprawdza, czy w kolekcji „x” nie pozostały żadne elementy. Język L opisujący operatory zagnieżdżone w Pascalu „początek koniec; ": @"^s*((? "zaczyna się+)+(? "-zaczyna się"kończy*; s*)+)*(? (początek)(? !))$".
Wygodniej jest opisać słownictwo języka w formie wyrażeń regularnych i rozpoznać język za pomocą CA. Dlatego ważna jest możliwość konwersji definicji języka w postaci wyrażeń regularnych na definicję w postaci CA. Transformację tę zaproponował Kenneth Thompson.
Skończona maszyna stanów to pięć (S, S, d, S 0 , F)
S jest skończonym zbiorem stanów.
S jest skończonym zbiorem ważnych sygnałów wejściowych.
d - funkcja przejścia. Odzwierciedla zbiór Sx(SÈ(e)) w zbiorze stanów niedeterministycznego automatu skończonego. W przypadku automatu deterministycznego funkcja przejścia odzwierciedla zbiór SxS w zbiorze stanów automatu. Innymi słowy, w zależności od stanu i symbolu wejściowego, d określa nowy stan maszyny.
S 0 - stan początkowy automatu skończonego, S 0 О S.
F jest zbiorem stanów końcowych automatu, F О S.
Działanie maszyny o skończonych stanach składa się z sekwencji kroków. Krok jest określany na podstawie stanu maszyny i symbolu wejściowego. Sam krok polega na zmianie stanu maszyny i odczytaniu kolejnego symbolu sekwencji wejściowej.
Istnieją następujące zasady konwertowania wyrażeń regularnych na maszynę stanów.
1 Wyrażenie regularne „e” zostaje przekształcone w automat dwóch stanów i e-przejścia pomiędzy nimi (rysunek 1).
Rysunek 1. – Automat do e-przejścia
2 Wyrażenie regularne składające się z jednego znaku „a” jest konwertowane na automat skończony o dwóch stanach i przejściu między nimi na podstawie sygnału wejściowego a (rysunek 2).
Rysunek 2. – Automat do przemieszczania się według symbolu a
3 Niech będzie wyrażenie regularne rs i maszyny skończone dla wyrażenia r i wyrażenie s zostało już zbudowane. Następnie dwie maszyny łączy się szeregowo. Rysunek 3 przedstawia oryginalne automaty dla języków r i s. Rysunek przedstawia automat rozpoznający konkatenację tych języków.
Maszyna do r Maszyna do s
Rysunek 3. – Automaty początkowe
Rysunek 4. – Maszyna do łączenia języków
4 Niech będzie wyrażenie regularne r | Dla wyrażenia r i wyrażenia s zbudowano już maszyny s i skończone stany (rysunek 3). Wtedy powstały automat musi mieć alternatywę dla wykonania jednego z dwóch automatów. Oznacza to, że automat dla wyrażenia r | s dla automatów dla r i s z rysunku 3 ma postać pokazaną na rysunku 5.
Rysunek 5. – Automat do łączenia języków
5 Niech dla skonstruowanego automatu skończonego r będzie istniało wyrażenie regularne r*. W tym przypadku wprowadzono dwa nowe stany, które umożliwiają ominięcie automatu wyrażeniowego r, a także wprowadzają e-przejście pomiędzy stanem końcowym i początkowym, aby umożliwić wielokrotne powtarzanie automatu r. Jeżeli dla wyrażenia regularnego r skonstruowany zostanie automat podobny do rysunku 3, to wyrażenie regularne r* odpowiada automatowi skończonemu przedstawionemu na rysunku 6.
Ustawienia
Zgodnie z twierdzeniem Kleene’a dowolne wyrażenie regularne można skojarzyć maszynę skończoną, która jest formalnym modelem algorytmu rozpoznawania leksemów oznaczanych danym wyrażeniem regularnym. W najbardziej ogólnym ujęciu maszyna stanowa-rozpoznawacz jest wyznaczany przez skończony zbiór charakterystycznych stanów strumienia wejściowego i przejść pomiędzy nimi. Zmiana stanu następuje w momencie odebrania symboli strumienia wejściowego z danego alfabetu zgodnie z funkcją przejścia, który określa możliwe kolejne stany na podstawie symbolu wejściowego i stanu bieżącego. Spośród możliwych stanów wyróżnia się ten początkowy(wstępny) i ostateczne(pozwalać) stany, w których automat skończony może znajdować się odpowiednio na początku i na końcu przetwarzania tokenów strumienia wejściowego. Jeżeli wejściowy ciąg symboli może wygenerować ciąg przejść, który może przenieść maszynę skończoną ze stanu początkowego do jednego ze stanów końcowych, to uważa się ją za dopuszczającą i należy do rozpoznawanego przez nią zbioru regularnego.
(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*
Tabela 1
| 0 | 1 | |
| Pytanie 1 | Pytanie 4 | Pytanie 2 |
| Pytanie 2 | Pytanie 3 | Pytanie 1 |
| Pytanie 3 | Pytanie 2 | Pytanie 4 |
| Pytanie 4 | Pytanie 1 | Pytanie 3 |
Kolumny tabeli przejść wskazują znaki alfabetu wejściowego, a wiersze odpowiadają aktualnym stanom DFA. Elementy każdej linii wskazują stany DFA, do którego musi przejść ze stanu bieżącego po otrzymaniu odpowiednich znaków alfabetu wejściowego. W szczególności z pierwszego wiersza tej tabeli przejść wynika, że otrzymanie symboli 0 i 1 w stanie początkowym Q1 powoduje translację DFA odpowiednio do stanów Q4 i Q2.
Rozpoznając sekwencję wejściową za pomocą tabeli przejść, łatwo jest prześledzić zmiany stanu DFA w celu ustalenia, czy jeden ze stanów dopuszczających został osiągnięty, czy nie. W szczególności dla wektora binarnego 01001000 z parzystą liczbą zer i jedynek rozważany DFA generuje następującą sekwencję przejść, gdzie każde przejście jest oznaczone symbolem alfabetu wejściowego, który je powoduje:
Q1 0 Q4 1 Q3 0 Q2 0 Q3 1 Q4 1 Q1 0 Q4 0 Q1
Ta sekwencja przejść kończy się stanem dopuszczającym Q1, zatem wektor binarny 01001000 należy do zbioru regularnego rozpoznawanego przez rozważany DFA i spełnia powyższe wyrażenie regularne.
Podsumowując, należy zauważyć, że uważa się za nieformalną metodę budowy
Dla dalszego badania właściwości automatów skończonych, a w szczególności dla rozwiązania problemu syntezy, ważne jest następujące twierdzenie.
Twierdzenie 7.7 (twierdzenie o determinacji). Dla dowolnego automatu skończonego można skonstruować równoważny deterministyczny automat skończony.
Aby udowodnić twierdzenie należy w pierwszej kolejności opisać algorytm budowy deterministycznego automatu skończonego z pierwotnego; po drugie, uzasadnienie tego algorytmu poprzez rygorystyczne udowodnienie, że rzeczywiście tworzy on maszynę stanów, która jest deterministyczna i równoważna oryginalnej. Tutaj prezentujemy jedynie algorytm budowy automatu deterministycznego.
Transformacja dowolnego automatu skończonego na równoważny automat deterministyczny odbywa się w dwóch etapach: najpierw usuwane są łuki z etykietą \lambda, a następnie przeprowadzane jest samo wyznaczanie.
1. Usuwanie przejść λ (łuki oznaczone \lambda).
Aby przejść z pierwotnego automatu skończonego M=(V,Q,q_0,F,\delta) do równoważnego automatu skończonego M"=(V,Q",q_0,F",\delta") bez przejść λ, należy wystarczy w oryginale dokonać następujących przekształceń na grafie M.
A. Wszystkie stany z wyjątkiem początkowego, w które wchodzą tylko łuki z etykietą \lambda, są usuwane; definiując w ten sposób zbiór Q” automatu skończonego M”. Jest oczywiste, że Q"\subseteq Q. Jednocześnie zakładamy, że stan początkowy pozostaje taki sam.
B. Zbiór łuków automatu skończonego M" i ich etykiet (a tym samym funkcja przejścia M" ) definiuje się następująco: dla dowolnych dwóch stanów p,r\in Q",~ p\to_(a)r zachodzi wtedy i tylko jeśli a \in V i na grafie M zachodzi jedna z dwóch rzeczy: albo istnieje łuk od p do r, którego etykieta zawiera symbol a, albo istnieje stan q taki, że p\Rightarrow_(\lambda)^( +)q i q\ to_(a)r W tym przypadku wierzchołek q, ogólnie rzecz biorąc, może nie należeć do zbioru Q”, tj. może zniknąć przy przejściu do automatu M” (rys. 7.11). Jeśli q\in Q” , to oczywiście łuk (q,r) zostanie zachowany w M” i symbol a będzie jednym z symboli należący do etykiety tego łuku (ryc. 7.12).
Zatem w M" zapisane są wszystkie łuki M, których etykiety są różne od \lambda i które łączą parę (wierzchołki) stanów ze zbioru Q" (nieskreślonego zgodnie z częścią a). Dodatkowo dla dowolnej trójki stanów p,q,r (niekoniecznie różnych!), takich, że p,r\in Q" i istnieje ścieżka o niezerowej długości od p do q, której etykieta jest równa do \lambda (tj. droga przez przejścia λ), a od q do r prowadzi łuk, którego etykieta zawiera symbol a alfabetu wejściowego; w M" tworzony jest łuk od p do r, etykieta który zawiera symbol a (patrz rys. 7.11).
V. Zbiór stanów końcowych F" automatu skończonego M" zawiera wszystkie stany q\in Q", czyli stany automatu skończonego M, które nie są kasowane zgodnie z paragrafem a, dla którego q\Rightarrow_(\lambda)^(\ ast) przechowuje q_f dla pewnego q_f\in F (tzn. albo sam stan q jest stanem końcowym automatu skończonego M, albo prowadzi od niego ścieżka o niezerowej długości wzdłuż łuków oznaczonych \lambda do jednego z końcowych stanów automatu automat skończony M) (ryc. 7.13) .
2. Samo określenie.
Niech M=(Q,V,q_0,F,\delta) będzie automatem skończonym bez przejść λ. Skonstruujmy deterministyczny automat skończony M_1 równoważny M.
Ten automat skończony definiuje się w ten sposób, że jego zbiór stanów jest zbiorem wszystkich podzbiorów zbioru stanów automatu skończonego M. Oznacza to, że każdy indywidualny stan automatu skończonego M_1 definiuje się jako pewien podzbiór zbioru stanów automatu skończonego M. W tym przypadku stan początkowy nowej maszyny o skończonych stanach (tj. M_1) jest podzbiorem singletonu zawierającym stan początkowy starej maszyny o stanach skończonych (tj. M), a stany końcowe nowej maszyny o stanach skończonych są takimi podzbiorami Q, które zawierają co najmniej jeden końcowy wierzchołek pierwotnego automatu skończonego M.
Odtąd, dopuszczając pewną swobodę wypowiedzi, stany automatu skończonego M_1 będziemy nazywać zbiorami stanów. Ważne jest jednak, aby jasno zrozumieć, że każdy taki zbiór stanów jest odrębnym stanem nowego automatu skończonego, a nie zbiorem jego stanów. Jednocześnie dla pierwotnego („starego”) automatu skończonego M jest to właśnie zbiór jego stanów. Mówiąc obrazowo, każdy podzbiór stanów starego automatu skończonego zostaje „zapadnięty” w jeden stan nowego automatu skończonego*.
*Formalnie powinniśmy zdefiniować zbiór Q_1 jako zbiór, który jest w korespondencji jeden do jednego ze zbiorem 2^Q, ale jeszcze wygodniej jest nam założyć, że Q_1 pokrywa się z 2^Q - w końcu zbiorem stanów automatu skończonego może być dowolny niepusty zbiór skończony.
Funkcja przejścia nowego automatu skończonego jest zdefiniowana w ten sposób, że ze zbioru stanów S poprzez symbol wejściowy a automat skończony M_1 przechodzi do zbioru stanów, będącego sumą wszystkich zbiorów stanów starego automatu skończonego, w które ten stary automat skończony ma symbol a z każdego zbioru stanów S. Zatem automat skończony M_1 jest z założenia deterministyczny.
Powyższy opis słowny można przełożyć na wzory w następujący sposób: budujemy maszynę skończoną M_1 tak, że
M_1=(Q_1,V,\(q_0\),F_1,\delta_1) , gdzie
\begin(cases)Q_1=2^Q,\quad F_1=\(T\colon\, T\cap F\ne\varnothing,~T\in2^Q\),\\ (\forall S\subseteq Q) (\forall a\in V)\Bigl(\delta_1(S,a)= \bigcup\limits_(q\in S)\delta(q,a)\Bigr). \end(przypadki)
Zwróćmy uwagę, że wśród stanów nowego automatu skończonego istnieje stan \varnothing oraz zgodnie z (7.8) \delta_1(\varnothing,a)=\varnothing dla dowolnego symbolu wejściowego a . Oznacza to, że będąc w takim stanie, maszyna stanów M_1 nie opuści go. Ogólnie rzecz biorąc, każdy stan q automatu skończonego taki, że dla dowolnego symbolu wejściowego a mamy \delta(q,a)=q, nazywany jest stanem pochłaniającym automatu skończonego. Zatem stan \varnothing deterministycznej maszyny skończonej M_1 jest absorbowany. Warto również zauważyć, że \delta_1(S,a)=\varnothing wtedy i tylko wtedy, gdy dla każdego q\in S (stany starej maszyny skończonej ze zbioru stanów S ) \delta(q,a)= \varnic , tj. na grafie M z każdego takiego stanu q, oznaczonego symbolem a, nie wychodzi żaden łuk.
Można wykazać, że otrzymany za pomocą takiego algorytmu automat skończony jest równoważny automatowi pierwotnemu.
Przykład 7.9. Wyznaczmy automat skończony pokazany na ryc. 7.14.
Równoważny automat skończony bez przejść λ pokazano na ryc. 7.15. Zauważ, że wierzchołek q_2 znika, ponieważ wchodzą do niego tylko „puste” łuki.
Aby wyznaczyć wynikowy automat, wcale nie jest konieczne zapisywanie wszystkich jego 2^3=8 stanów, z których wiele może być nieosiągalnych ze stanu początkowego \(q_0\) . Aby otrzymać stany osiągalne z \(q_0\) i tylko te, posłużymy się tzw. metodą ciągnącą.
Metodę tę można ogólnie opisać w następujący sposób.
W początkowym automacie skończonym (bez pustych łuków) definiujemy wszystkie zbiory stanów, które są osiągalne od stanu początkowego, tj. dla każdego symbolu wejściowego a znajdujemy zbiór \delta(q_0,a) . Każdy taki zbiór w nowym automacie jest stanem dostępnym bezpośrednio ze stanu początkowego.
Dla każdego ze zdefiniowanych zbiorów stanów S i każdego symbolu wejściowego a znajdujemy zbiór \textstyle(\mathop(\bigcup\limits_(q\in S) \delta(q,a))\limits^(\phantom( A)^(.))) . Wszystkie stany uzyskane na tym etapie będą stanami nowego (deterministycznego) automatu, osiągalnego od początkowego wierzchołka po ścieżce o długości 2. Opisaną procedurę powtarzamy do momentu, aż nie pojawią się żadne nowe stany ustalone (w tym puste!). Można wykazać, że daje to wszystkie stany automatu skończonego M_1, które są osiągalne ze stanu początkowego \(q_0\).
Dla skończonej maszyny stanów z rys. 7.15 mamy:
\begin(aligned)& \delta_1(\(q_0\),a)=\(q_1\);\qquad \delta_1(\(q_0\),b)=\(q_1,q_3\);\\ & \ delta_1(\(q_1\),a)=\(q_1\);\qquad \delta_1(\(q_1\),b)=\(q_1\);\\ & \delta_1(\(q_1,q_3\) ,a)= \delta(q_1,a)\cup \delta(q_3,a)= \(q_1\)\cup\(q_1\)=\(q_1\);\\ & \delta_1(\(q_1, q_3\),b)= \delta(q_1,b)\cup \delta(q_3,b)= \(q_1\)\cup\(q_1\)=\(q_1\). \end(wyrównane)
Ponieważ nie pojawiły się żadne nowe zbiory stanów, procedura „wyciągania” kończy się w tym miejscu i otrzymujemy wykres pokazany na rys. 7.16.
Regularny dodatek językowyJedną z ważnych teoretycznych konsekwencji twierdzenia o determinacji jest następujące twierdzenie.
Twierdzenie 7.8. Dopełnieniem języka regularnego jest język regularny.
Niech L będzie językiem regularnym w alfabecie V. Wtedy uzupełnieniem języka L (jako zbioru słów) jest język \overline(L)=V^(\ast)\setminus L .
Zgodnie z Twierdzeniem 7.7 dla języka regularnego L można skonstruować deterministyczny automat skończony M, który dopuszcza L. Ponieważ w automacie deterministycznym z każdego wierzchołka dla każdego symbolu wejściowego jest zdefiniowane przejście do dokładnie jednego wierzchołka, to niezależnie od tego, jaki łańcuch x znajduje się w alfabecie V, istnieje dla niego unikalna ścieżka w M, rozpoczynająca się od stanu początkowego, na którym znajduje się Łańcuch x jest czytany. Jest oczywiste, że łańcuch x jest dozwolony przez automat M , czyli x\in L(M) , wtedy i tylko wtedy, gdy ostatni stan określonej ścieżki jest ostateczny. Wynika z tego, że łańcuch x\notin L(M) wtedy i tylko wtedy, gdy ostatni stan określonej ścieżki nie jest ostateczny. Ale potrzebujemy tylko skończonego automatu M”, który dopuszcza łańcuch x wtedy i tylko wtedy, gdy nie jest to dozwolone przez pierwotny automat skończony M. Zatem zamieniając każdy stan końcowy M w stan niekońcowy i odwrotnie, otrzymujemy automat deterministyczny dopuszczający dodanie języka L .
Sprawdzone twierdzenie pozwala nam zbudować automat skończony, który nie dopuszcza określonego zbioru łańcuchów, stosując następującą metodę: najpierw budujemy automat dopuszczający dany zbiór łańcuchów, następnie go wyznaczamy i idziemy do automatu w celu dodania jako wskazane w dowodzie Twierdzenia 7.8.
Przykład 7.10. A. Zbudujmy automat skończony, który akceptuje wszystkie łańcuchy w alfabecie \(0;1\) z wyjątkiem łańcucha 101.
Najpierw zbudujmy automat skończony, który pozwala na pojedynczy łańcuch 101. Automat ten pokazano na ryc. 7.17.
Automat ten jest quasi-deterministyczny, ale nie deterministyczny, ponieważ nie jest w pełni zdefiniowany. Wyznaczmy to i otrzymajmy deterministyczny równoważny automat skończony pokazany na rys. 7.18.
I wreszcie, przechodząc do dodawania (i zmiany nazwy stanów), otrzymujemy automat pokazany na ryc. 7.19.
Należy zauważyć, że w powstałym automacie wszystkie wierzchołki, z wyjątkiem wierzchołka s_3, są ostateczne.
Należy również zauważyć, że przejście do dopełnienia, które jest omówione w dowodzie Twierdzenia 7.8, można przeprowadzić tylko w automacie deterministycznym. Gdybyśmy zamienili role wierzchołków końcowych i niekońcowych w automacie pokazanym na rys. 7.17, otrzymalibyśmy automat obsługujący język \(\lambda,1,10\) , który nie jest - jak łatwo sobie wyobrazić - zbiorem wszystkich łańcuchów innych niż łańcuch 101.
Należy również zauważyć, że skończona maszyna stanów na rys. Wersja 7.19 zezwala na wszystkie ciągi, które zawierają wystąpienie ciągu 101, ale nie pasują do samego tego ciągu. Oto na przykład łańcuch nośny ścieżki 1011: s_0,s_1,s_2,s_3,t.
B. Zbudujmy automat skończony, który akceptuje wszystkie łańcuchy w alfabecie \(0;1\) z wyjątkiem tych, które zawierają wystąpienie łańcucha 101. Rozważmy język L, którego każdy łańcuch zawiera wystąpienie łańcucha 101. Można go zdefiniowany w następujący sposób:
L=(0+1)^(\ast)101(0+1)^(\ast).
Musimy zbudować automat uzupełniający język L.
W tym przypadku, korzystając bezpośrednio z wyrażenia regularnego, łatwo jest zbudować automat skończony, który akceptuje język L (ryc. 7.20).
Następnie przeprowadzimy determinację metodą „pull”. Wynik oznaczenia przedstawiono na ryc. 7.21.
Aby całkowicie rozwiązać problem, wszystko, co pozostaje, znajduje się na ryc. 7.21 zamień role wierzchołków końcowych i niekońcowych (ryc. 7.22).
V. Omówmy ideę zbudowania automatu skończonego, który pozwala na te i tylko te łańcuchy w alfabecie \(0;1\), które nie zaczynają się od łańcucha 01 i nie kończą się na łańcuchu 11 (czyli łańcuchy forma 01x i łańcuchy typu y11 są niedozwolone, niezależnie od tego, jakie były łańcuchy x,y\in\(0;1\) ).
W tym przypadku dopełnieniem języka, dla którego konieczne jest zbudowanie automatu skończonego, jest zbiór wszystkich takich łańcuchów zer i jedynek, które zaczynają się od łańcucha 01 lub kończą na łańcuchu 11. Automat, który pozwala na taki zbiór łańcuchy jest skonstruowany jako automat do łączenia 01(0+1)^(\ ast)+(0+1)^(\ast)11 w taki sam sposób, jak opisano w dowodzie twierdzenia Kleene’a (patrz Twierdzenie 7.6).
Z własności, że klasa języków regularnych jest zamknięta ze względu na dopełnienie (patrz Twierdzenie 7.8) bezpośrednio wynika, że klasa ta jest zamknięta ze względu na przecięcie, teorię mnogości i różnicę symetryczną.
Wniosek 7.3. Dla dowolnych dwóch języków regularnych L_1 i L_2 prawdziwe są następujące stwierdzenia:
1) przecięcie L_1\cap L_2 jest regularne;
2) różnica L_1\setminus L_2 jest regularna;
3) różnica symetryczna L_1\vartriangle L_2 jest regularna.
Ważność stwierdzeń wynika z tożsamości:
\begin(aligned) &(\scriptstyle(\mathsf(1))))\quad L_1\cap L_2= \overline(\overline(L_1) \cup\overline(L_2))\,;\\ &(\scriptstyle (\mathsf(2))))\quad L_1\setminus L_2= L_1\cap \overline(L_2)\,;\\ &(\scriptstyle(\mathsf(3))))\quad L_1\,\trójkąt\ ,L_2 = (L_1\kubek L_2)\setminus (L_1\nasadka L_2).\end(wyrównane)
Po pierwsze, uzyskane wyniki pozwalają stwierdzić, że klasą języków regularnych ze względu na operacje sumowania, przecięcia i dodawania jest algebra Boole'a, w której jednostką jest język uniwersalny, a zero jest językiem pustym. Po drugie, te właściwości algebraiczne rodziny języków regularnych pozwalają nam rozwiązać ważny problem uznania równoważności dwóch dowolnych automatów skończonych.
Zgodnie z definicją 7.10 maszyny o skończonych stanach są równoważne, jeśli akceptowane przez nie języki są takie same. Zatem, aby sprawdzić równoważność automatów M_1 i M_2, wystarczy udowodnić, że różnica symetryczna języków L(M_1) i L(M_2) jest pusta. Aby to zrobić, wystarczy skonstruować automat, który dopuszcza tę różnicę i upewnia się, że język, który dopuszcza, jest pusty. Ogólnie rzecz biorąc, problem rozpoznania, że język maszyny stanowej jest pusty, nazywany jest problemem pustki maszyny stanowej. Aby rozwiązać ten problem, wystarczy znaleźć zbiór stanów końcowych automatu, które są osiągalne ze stanu początkowego. Ponieważ maszyna skończona jest grafem skierowanym, problem ten można rozwiązać, na przykład, stosując przeszukiwanie wszerz. Język dozwolony przez skończoną maszynę stanów jest pusty wtedy i tylko wtedy, gdy zbiór stanów końcowych osiągalnych ze stanu początkowego jest pusty. W praktyce preferuje się rozpoznawanie równoważności automatów skończonych za pomocą algorytmu minimalizacji, ale teraz ważne jest dla nas podkreślenie, że podstawowa możliwość rozwiązania problemu równoważności wynika z Twierdzenia 7.7 i jego konsekwencji algebraicznych.
