Języki, automaty i obliczenia/Wykład 7: Twierdzenie Kleene'ego. Własności języków i gramatyk regularnych

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

W wykładzie udowodnimy twierdzenie Kleene'ego, które orzeka, że rodzina języków regularnych jest identyczna z rodziną języków rozpoznawanych przez automaty o skończonej liczbie stanów. Przedstawimy własności języków regularnych i gramatyk typu (3). Na koniec uzasadnimy, że rodziny języków regularnych, rozpoznawalnych oraz generowanych przez gramatyki typu (3), są tożsame.

Twierdzenie Kleene

Stephen Cole Kleene (1909-1994)
Zobacz biografię

Wiemy już, z poprzednich wykładów, że rodzina wyrażeń regularnych

określa rodzinę języków regularnych. Celem pierwszej części tego wykładu jest ustalenie związku pomiędzy rodziną języków regularnych a rodziną języków rozpoznawanych przez automaty o skończonej liczbie stanów. Twierdzenie, udowodnione przez S.C.Kleene'ego w roku 1956, orzeka, iż te dwie rodziny języków są identyczne.

Twierdzenie 1.1.

Dla dowolnego skończonego alfabetu

Dowód

Dowód pierwszej części twierdzenia, czyli inkluzja , będzie prowadzony zgodnie ze strukturą definicji rodziny języków regularnych .

1. Język pusty jest rozpoznawany przez dowolny automat w którym zbiór stanów końcowych jest pusty.

2. Język a złożony z dowolnej litery jest rozpoznawany przez automat End of proof.gif
Rysunek 1

Dla dalszej części dowodu ustalmy, iż dane są języki rozpoznawane odpowiednio przez automaty deterministyczne , gdzie

3. Sumę mnogościową języków , czyli język rozpoznaje automat , dla którego , , oraz dla dowolnego stanu i litery funkcja przejść określona jest równością

4. Katenację języków , czyli język rozpoznaje automat , dla którego oraz dla dowolnego stanu i litery funkcja przejść określona jest następująco:

a zbiorem stanów końcowych jest

5. Załóżmy, że język rozpoznaje automat . Określimy automat niedeterministyczny, który będzie rozpoznawał gwiazdkę Kleene języka , czyli Automat niedeterministyczny , w którym

rozpoznaje język język Dowód tego faktu jest indukcyjny i pozostawiamy go na ćwiczenia. Zauważmy teraz, że język rozpoznaje automat

Rysunek 2

Ponieważ , to korzystając z udowodnionej już zamkniętości języków rozpoznawanych ze względu na sumę mnogościową, stwierdzamy, że istnieje automat rozpoznający język .

Zatem dowód inkluzji jest zakończony.

Przejdziemy teraz do dowodu inkluzji .

Niech oznacza dowolny język rozpoznawany przez automat Dowód polega na rozbiciu języka na fragmenty, dla których stwierdzenie, że są to języki regularne będzie dość oczywiste. Natomiast sam język będzie wynikiem operacji regularnych określonych na tych właśnie fragmentach. Poniżej przeprowadzamy defragmentację języka

Dla niech

Jest to język złożony ze słów, które przeprowadzają stan automatu w stan . Ogół liter alfabetu przeprowadzających stan w oznaczymy przez

Dla stanów i zbioru niech

Jest to język, który można przedstawić graficznie następująco:

Rysunek 3

Na koniec przyjmijmy

określony dla i

Język ten jest graficznie interpretowany poniżej.

Rysunek 4

Wprost z określeń wynika, że wszystkie wprowadzone powyżej języki są regularne, czyli należą do rodziny . Dowód tego faktu przebiega indukcyjnie ze względu na liczbę elementów zbiorów i . Szczegóły tego dowodu pominiemy. Natomiast warto wskazać rolę, jaką spełniają w dowodzie wprowadzone wyżej języki. A mianowicie:



Tę ostatnią równość przedstawia poniższy rysunek.

Rysunek 5

co graficznie można przedstawić następująco:

Rysunek 6

Dochodzimy więc do konkluzji, iż jezyki oraz są regularne. W szczególności zatem regularny jest język .

Język możemy przedstawić w następującej postaci:

co w połączeniu z ustaleniami punktu 3 z poprzedniej części dowodu uzasadnia tezę, że język należy do rodziny .

Własności języków regularnych i gramatyk regularnych

W tej części wykładu omówimy własności rodziny języków i gramatyk regularnych, czyli typu (3) w hierarchii Chomsky'ego. Ustalimy też związek pomiędzy językami a gramatykami regularnymi. Zbadamy zamkniętość rodziny języków regularnych ze względu na operacje mnogościowe, czyli ze względu na sumę, przecięcie, różnicę i uzupełnienie. Rozpoczniemy jednak tę część wykładu od wprowadzenia jednoargumentowego działania na słowach zwanego odbiciem zwierciadlanym.

Definicja 2.1.

Odbiciem zwierciadlanym słowa nazywamy słowo . Odbiciem zwierciadlanym języka nazywamy język

Twierdzenie 2.1.

Rodzina jest zamknięta ze względu na:

(1) sumę mnogościową, przecięcie, różnicę i uzupełnienie,
(2) katenację i operację iteracji
(3) obraz homomorficzny,
(4) podstawienie regularne,
(5) przeciwobraz homomorficzny,
(6) odbicie zwierciadlane.

Dowód

1. Zamkniętość rodziny języków ze względu na sumę mnogościową wynika z twierdzenia Kleene'ego. Automat akceptujący iloczyn języków otrzymujemy, zmieniając odpowiednio zbiór stanów końcowych w automacie rozpoznającym sumę. Bowiem pozostając przy oznaczeniach punktu 3 z dowodu twierdzenia Kleene'ego, automat gdzie , rozpoznaje język Jeśli automat akceptuje język , to automat akceptuje język Ostatnia własność implikuje zamkniętość ze względu na uzupełnienie.

2 Z twierdzenia Kleene'ego, punkt 4 i 5, wynika zamkniętość ze względu na katenację i operację iteracji .

3. Niech będzie homomorfizmem. Dowód implikacji

przeprowadzimy zgodnie ze strukturą definicji rodziny języków regularnych. Dla i dla gdzie jest dowolną literą alfabetu , implikacja jest oczywista. W pierwszym przypadku obrazem homomorficznym jest język pusty, a w drugim język , gdzie jest pewnym słowem nad alfabetem . Dla dowolnych języków regularnych prawdziwe są równości:

  • ,
  • ,

co kończy dowód tego punktu.

4. Uzasadnienie jest podobne jak dla homomorfizmu. Jedyna różnica tkwi w tym, że dla podstawienia regularnego i dla dowolnej litery wartość podstawienia na literze jest pewnym językiem regularnym , a nie słowem jak w przypadku homomorfizmu.

5. Niech będzie homomorfizmem. Aby udowodnić implikację

odwołamy się do własności, że dla języka istnieje skończony monoid i homomorfizm taki, że Dla

homomorfizmu mamy równość:

Korzystając teraz z punktu 4 twierdzenia 1.2 z wykładu 3 (patrz twierdzenie 1.2. wykład 3), wnioskujemy, że .

6. Wykorzystamy tutaj zapis języka regularnego przez wyrażenie regularne. Niech dla języka wyrażenie regularne będzie takie, że . Wtedy język jest opisany przez wyrażenie regularne , które uzyskujemy z przez odbicie zwierciadlane, a dokładniej odwrócenie kolejności katenacji w każdej sekwencji tego działania występującej w wyrażeniu regularnym.

End of proof.gif

W wykładzie drugim wprowadziliśmy pojęcie gramatyki. Wracamy do tego pojęcia, a w szczególności do gramatyki typu (3), czyli regularnej. Przypomnijmy, że produkcje takiej gramatyki mają postać:

gdzie . Gramatykę typu (3), nazywamy inaczej lewostronną lub lewoliniową. Określa się też gramatykę regularną prawostronną (prawoliniową). Jest to gramatyka , której produkcje są postaci:

gdzie . Jeśli język jest generowany przez gramatykę typu (3) (lewoliniową), to jego odbiciem zwierciadlanym jest , gdzie jest gramatyką prawoliniową, którą uzyskuje się z gramatyki przez odbicie zwierciadlane prawych stron produkcji. Oznacza to, iż zmieniamy produkcje według następujących zasad:

zastępujemy przez
zastępujemy przez

Oczywiście, jeśli jest językiem generowanym przez gramatykę prawoliniową, to jest generowany przez odpowiednią gramatykę lewoliniową.

Podamy teraz charakterystykę rodziny języków regularnych przez rodzinę gramatyk prawoliniowych.

Twierdzenie 2.2.

Niech . Język wtedy i tylko wtedy, gdy dla pewnej gramatyki prawoliniowej .

Dowód

Załóżmy, że automat rozpoznaje język . Definiujemy gramatykę przyjmując oraz określając w następujący sposób zbiór produkcji

Dla dowolnego stanu i słowa prawdziwa jest równoważność

Dowód przeprowadzimy indukcyjnie ze względu na długość słowa . Niech dla pewnego . Z definicji zbioru produkcji wynika równoważność

Rozważmy teraz oraz . Z założenia indukcyjnego

wynika, że

oraz, że wtedy i tylko wtedy, gdy A więc fakt, że jest równoważny temu, że . A to z kolei równoważne jest

i ostatecznie równoważne faktowi, że . A zatem dowodzona równoważność jest prawdziwa dla , ponieważ

Dla mamy co kończy dowód w jedną stronę.

Rozważmy teraz język generowany przez pewna gramatykę prawoliniową . Skonstruujemy gramatykę równoważną i taką, w której wszystkie produkcje są postaci lub , gdzie . Będziemy zamieniać produkcje występujące w gramatyce na inne, o żądanej postaci, zgodnie z następująmi zasadami:

1. Produkcje typu , gdzie

Z symbolem nieterminalnym kojarzymy określony poniżej zbiór

oraz zbiór produkcji

Dla każdego takiego symbolu usuwamy ze zbioru wszystkie produkcje i wprowadzamy na to miejsce wszystkie produkcje ze zbioru .

2. Produkcje typu dla .

Jeśli produkcja taka występuje w i , to do alfabetu nieterminalnego dodajemy nowy symbol . Następnie ze zbioru usuwamy powyższą produkcję i dodajemy dwie nowe:

Zauważmy, że jeśli , to .

3. Produkcje typu dla

Jeśli , przy czym , to do alfabetu nieterminalnego dodajemy nowe symbole , produkcję usuwamy ze zbioru i

dodajemy produkcje:

Po opisanych powyżej trzech modyfikacjach gramatyki generowany język, co łatwo zauważyć, nie ulega zmianie. Zatem skonstruowana gramatyka jest równoważna wyjściowej. Dla otrzymanej gramatyki określamy teraz automat niedeterministyczny , przyjmując , oraz i definiując następująco funkcję przejść: Przjmując jako zbiór stanów końcowych, stwierdzamy, że automat rozpoznaje język

Uzyskany rezultat, w świetle równości , kończy dowód twierdzenia.

End of proof.gif

Algorytmiczną stroną równoważności udowodnionej w powyższym twierdzeniu zajmiemy się w następnym wykładzie. Przykłady ilustrujące twierdzenie zamieszczamy poniżej.

Przykład 2.1.

1. Niech będzie automatem takim, że

, a graf przejść wygląda następująco:
Rysunek 7

Gramatyka , gdzie

akceptuje język .

Zauważmy, że język

2. Niech , gdzie

Gramatykę przekształcamy w równoważną gramatykę

gdzie

Niedeterministyczny automat , gdzie graf przejśc wygląda następująco:

Rysunek 8


Wykorzystując udowodnione do tej pory własności rodziny języków generowanych przez gramatyki regularne, uzasadnimy teraz, iż ta właśnie rodzina, czyli ogół języków typu (3) w hierarchii Chomsky'ego pokrywa się z rodziną .

Twierdzenie 2.3.

Dla dowolnego alfabetu rodziny języków regularnych oraz języków generowanych przez gramatyki regularne są równe, czyli .

Dowód

Odbicie zwierciadlane dowolnego języka , czyli język należy również do rodziny , co oznacza, że . Na podstawie twierdzenia 2.2. (patrz twierdzenie 2.2.) istnieje więc gramatyka prawoliniowa taka, że . A stąd wniosek, że dla pewnej gramatyki typu (3). Zatem .

Rozważmy teraz język typu (3), czyli dla pewnej gramatyki regularnej. A więc dla pewnej gramatyki prawoliniowej i . Z twierdzenia Kleene'ego wynika, że i ostatecznie , co kończy dowód twierdzenia.

End of proof.gif

Zamkniemy rozważania następującą konkluzją podsumowującą główne rezultaty tego wykładu.

Dla dowolnego skończonego alfabetu prawdziwe są równości:

czyli wprowadzone pojęcia rodziny języków regularnych, rozpoznawalnych oraz generowanych przez gramatyki typu (3) są tożsame.