Języki, automaty i obliczenia/Wykład 11: Automat ze stosem

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Automat ze stosem

W tym wykładzie określimy automat ze stosem rozpoznający języki bezkontekstowe. Wprowadzimy dwie definicje rozpoznawania języków przez automat ze stosem oraz omówimy ważną podklasę języków bezkontekstowych, mianowicie języków rozpoznawanych przez deterministyczne automaty ze stosem. Uzasadnimy też fakt, iż rodzina języków rozpoznawana przez automaty ze stosem pokrywa się z rodziną jezyków bezkontekstowych.

Automaty ze stosem to systemy rozpoznające języki bezkontekstowe. Ich działanie jest nieco bardziej skomplikowane niż działanie automatu skończenie stanowego. Poza możliwością zmiany stanu pod wpływem czytanego symbolu umieszczonego na taśmie wejściowej automat ten posiada także taśmę stosu, na którą może wpisywać słowa, jak i odczytywać pojedynczy symbol znajdujący się na wierzchu stosu.

Definicja 1.1

Automatem ze stosem nad alfabetem nazywamy system , w którym:

- jest alfabetem,

- jest dowolnym skończonym i niepustym zbiorem zwanym alfabetem stosu (niekoniecznie rozłącznym z ),

- jest dowolnym, skończonym i niepustym zbiorem zwanym zbiorem stanów,

jest funkcją przejść, której wartościami są skończone podzbiory (także zbiór pusty),

jest stanem początkowym,

symbolem początkowym stosu,

zbiorem stanów końcowych.

Badając działanie automatu ze stosem, wygodniej jest, zamiast funkcji przejść , rozważać skończoną relację zwaną relacją przejść. Elementy tej relacji nazywane są prawami. Relacja jest zatem skończonym zbiorem praw o następującej postaci:

  1. dla ,
  2. dla .

Często, używając relacji przejść, oznaczamy automat ze stosem jako układ:

Prawo będziemy reprezentować grafem:

Rysunek 1

Napis oznacza, iż symbol pobrany ze stosu wymieniany jest na słowo utworzone nad alfabetem stosu .

Natomiast prawo interpretowane jest graficznie jako:

Rysunek 2

Działanie automatu ze stosem zależne jest, jak wspomnieliśmy we wstępie wykładu, nie tylko od czytanego przez automat słowa, ale także od symbolu znajdującego się na wierzchu stosu. Poniżej przedstawiamy graficznie te zależności.


Prawo dla słowa określające działanie automatu interpretujemy w ten sposób, że automat, będąc w stanie po przeczytaniu litery (ze słowa wejściowego) i symbolu ze stosu, zmienia stan na oraz zastępuje na stosie literę słowem w ten sposób, że ostatnia litera tego słowa, symbol , jest na wierzchu stosu. Ten właśnie symbol będzie pobrany ze stosu przy kolejnym "ruchu" automatu, zgodnie z zasadą last in, first out. Ilustruje tę zasadę animacja, która jest zamieszczona będzie w dalszej części tego wykładu.

Dla precyzyjnego opisu działania automatu ze stosem wprowadza się pojęcie konfiguracji automatu, poprzedzając to pojęcie określeniem konfiguracji wewnętrznej.

Definicja 1.2

Konfiguracją wewnętrzną automatu ze stosem nazywamy dowolną parę taką, że jest stanem, w którym automat znajduje się aktualnie, a słowem zapisanym na stosie tak, że litera będąca na wierzchu stosu jest ostatnią literą tego słowa.

Konfiguracją automatu ze stosem nazywamy trójkę

gdzie jest konfiguracją wewnętrzną, a słowem wejściowym.

Wprowadzone pojęcia wykorzystamy do określenia działania automatu ze stosem dla dowolnych słów wejściowych i dowolnych słów znajdujących się na stosie. W tym celu rozszerzymy odpowiednio relację przejść , określając ją na zbiorze konfiguracji i oznaczając symbolem . Przyjmujemy dla dowolnych słów i litery , dla dowolnego słowa i oraz dla dowolnych stanów , że zachodzi relacja

wtedy i tylko wtedy, gdy .

Zwrotne i przechodnie domknięcie tej relacji nazywamy przejściem lub poprawnym obliczeniem automatu i oznaczamy symbolem .

Dla dowolnego słowa przyjmujemy oznaczenie , jeśli ma miejsce . Prawdziwa jest wówczas następująca równość:

Mówimy, że konfiguracja wewnętrzna automatu ze stosem jest osiągalna z konfiguracji wewnętrznej , jeśli istnieje takie słowo , że

Zdefiniujemy teraz język rozpoznawany przez automat ze stosem. W literaturze spotkać można kilka równoważnych definicji rozpoznawania. W naszym wykładzie wprowadzimy dwie, używane najczęściej:

  1. rozpoznawanie poprzez stany końcowe (wyróżniony zbiór stanów końcowych ),
  2. rozpoznawanie poprzez pusty stos.

Definicja 1.3

Niech będzie automatem ze stosem. Językiem rozpoznawanym przez automat poprzez stany końcowe nazywamy zbiór

Językiem rozpoznawanym przez automat poprzez pusty stos nazywamy zbiór

Używając drugiego określenia rozpoznawania, w definicji automatu ze stosem pomija się zbiór stanów końcowych .

Przykład 1.1

Poniższa animacja ilustruje działanie automatu ze stosem. Przedstawiony grafem automat ze stosem , w którym alfabet stosu rozpoznaje język bezkontekstowy

Zauważmy, że automat ten rozpoznaje ten sam język zarówno zarówno przez stany końcowe ( ), jak i w sensie rozpoznawania przez pusty stos.

W ogólności dla ustalonego automatu ze stosem wprowadzone wyżej dwa sposoby rozpoznawania niekoniecznie prowadzą do tego samego języka. Jednak są one równoważne, o czym przekonuje następujące twierdzenie, w dowodzie którego konstruujemy odpowiednie automaty ze stosem.

Twierdzenie 1.1

Język jest rozpoznawany przez automat ze stosem przez stany końcowe wtedy i tylko wtedy, gdy jest rozpoznawany przez automat ze stosem poprzez pusty stos.

Dowód

Załóżmy, że automat rozpoznaje przez stany końcowe język . Wówczas automat

w którym symbol jest spoza alfabetu , stany nie należą do , a relacja przejść określona jest poniżej

rozpoznaje język przez pusty stos.

Na odwrót, jeśli automat ze stosem rozpoznaje poprzez pusty stos język , to automat

w którym symbol jest spoza alfabetu , stany nie należą do , a relacja przejść określona jest poniżej

rozpoznaje język poprzez stany końcowe.

End of proof.gif

Zdefiniujemy i omówimy teraz deterministyczne automaty ze stosem. W odróżnieniu od automatów skończenie stanowych deterministyczne automaty ze stosem posiadają mniejsze możliwości rozpoznawania języków niż automaty, które dopuszczają przejścia niedeterministyczne.

Definicja 1.4

Automat ze stosem nazywamy deterministycznym, jeśli dla każdej konfiguracji wartość funkcji jest zbiorem co najwyżej jednoelementowym, czyli oraz jeśli , to dla każdego .

A więc deterministyczny automat ze stosem ma możliwość co najwyżej jednego przejścia z dowolnej konfiguracji oraz jeśli istnieje przejście dla określonego stanu i symbolu ze stosu pod wpływem słowa pustego, to jest ono jedynym możliwym dla tego układu w tym automacie.

Język rozpoznawany przez deterministyczny automat ze stosem nazywamy językiem deterministycznym.

O tym, że, w przeciwieństwie do klasy języków regularnych, języki rozpoznawane przez deterministyczne automaty ze stosem stanowią właściwą podklasę wszystkich języków akceptowanych przez automaty ze stosem, przekonuje przykład.

Przykład 1.2

Język rozpoznawany przez automat ze stosem opisany grafem

Rysunek 3

nie jest językiem deterministycznym. Zauważmy bowiem, że deterministyczny automat ze stosem, aby zaakceptować słowo , dla kontrolowania ilości liter i wykorzystuje stos, wprowadzając przy czytaniu każdej litery ustalony symbol na stos, na przykład i usuwając sekwencyjnie te symbole przy czytaniu liter . Dla zaakceptowania słowa podobne postępowanie prowadzi do wpisywania na stos słowa z alfabetu stosu dla każdej litery i usuwaniu pojedynczego symbolu przy czytaniu . Jest to jedyny sposób kontroli ilości liter, a opisane działanie automatu jest źródłem jego istotnej niedeterministyczności. Bez trudu można zauważyć, że każdy automat ze stosem rozpoznający język będzie zawierać ten niedeterministyczny układ w swojej strukturze.

Aby lepiej uchwycić istotę tego niedeterminizmu, zauważmy, że automat ze stosem określony grafem

Rysunek 4

rozpoznaje język i jest deterministyczny.


Każdy język rozpoznawany przez deterministyczny automat ze stosem jest oczywiście (dlaczego?) jednoznaczny. Jednoznaczność języka nie implikuje jednak jego deterministyczności, o czym przekonuje zamieszczony poniżej przykład.

Przykład 1.3

Język , który jest rozpoznawany przez automat ze stosem z poprzedniego przykładu, nie jest, jak wiemy, deterministyczny, ale jest jednoznaczny.

Gramatyki bezkontekstowe i automaty ze stosem

Automaty ze stosem charakteryzują rodzinę języków bezkontekstowych w tym samym sensie, w jakim automaty skończenie stanowe charakteryzują języki regularne.

Twierdzenie 2.1

Rodzina języków rozpoznawanych przez automaty ze stosem jest równa rodzinie języków bezkontekstowych .

Dowód

(szkic)

Dla dowodu, że każdy język bezkontekstowy jest rozpoznawany przez odpowiedni automat ze stosem, rozważmy gramatykę bezkontekstową w postaci normalnej Greibach i załóżmy, że słowo puste nie należy do języka generowanego przez tę gramatykę. Podamy konstrukcję automatu ze stosem , który, jak można wykazać, akceptuje poprzez pusty stos język . Niech

gdzie funkcja określona jest następująco. Dla dowolnych

oraz ma wartość równą zbiorowi pustemu we wszystkich pozostałych przypadkach.

Jest to więc automat o jednym stanie , alfabetem wejściowym jest alfabet terminalny , alfabetem stosu jest suma mnogościowa alfabetu symboli nieterminalnych i terminalnych , a symbol początkowy stosu jest symbolem startowym gramatyki. Istotą działania automatu jest symulacja lewostronnego wyprowadzenia w gramatyce Pełne uzasadnienie podanej konstrukcji znajduje sie na końcu tego wykładu, w części "dla zainteresowanych".

Załóżmy teraz, że automat akceptuje poprzez pusty stos język . Konstrukcja gramatyki bezkontekstowej , która generuje ten sam język przebiega następująco. Niech , gdzie . Wprowadzamy do zbioru praw wyłącznie następujące prawa:

  1. dla wszystkich stanów ,
  2. dla dowolnych stanów jeśli ,
  3. jeśli .

Mamy więc następującą równoważność:

która w szczególności dla przyjmuje postać

i oznacza dla gramatyki wymazywanie symboli nieterminalnych, a dla automatu wymazywanie symboli stosu.

Skonstruowana gramatyka odtwarza działanie automatu działającego pod wpływem słowa wejściowego . Pełne uzasadnienie podanej konstrukcji znajduje się na końcu tego wykładu, w części "dla zainteresowanych".

End of proof.gif

Z konstrukcji przedstawionej w szkicu dowodu twierdzenia wynika, że każdy język bezkontekstowy może być rozpoznawany poprzez pusty stos przez automat ze stosem o jednym stanie. Określenie algorytmów na podstawie powyższego twierdzenia proponujemy jako ćwiczenie.

Powróćmy na moment do języka Łukasiewicza. Język ten oraz jego gramatyka zostały wprowadzone podczas pierwszego wykładu poświęconego językom bezkontekstowym. Każde słowo, generowane przez tę gramatykę, jest pewnym wyrażeniem algebraicznym zapisanym w notacji polskiej, prefiksowej, bez użycia nawiasów. Bez trudności można określić gramatykę bezkontekstową, która generuje język Łukasiewicza, w którym słowa zapisywane są w wersji postfiksowej. Wystarczy bowiem przyjąć: , gdzie , , oraz . Język Łukasiewicza jest więc teraz zbiorem

Oczywiście język ten jest rozpoznawany przez odpowiedni automat ze stosem. Określeniem takiego automatu zajmiemy się podczas ćwiczeń. Warto zauważyć, że rozpoznając słowa języka Łukasiewicza w postfiksowej postaci, automat ze stosem działa dokładnie tak, jak obliczane są wartości wyrażeń arytmetycznych we współczesnych procesorach. Automat ze stosem, czytając wyrażenie od lewej do prawej, zapisuje wyniki częściowe na stosie, a operacje wykonywane są zawsze na ostatnich elementach stosu.

Dla bardziej dociekliwych studentów proponujemy poniżej pełny dowód twierdzenia 2.1 orzekajacego, że języki rozpoznawane przez automaty ze stosem to dokładnie języki bezkontekstowe.

Dla zainteresowanych



Dowod

Dla dowodu, że każdy język bezkontekstowy jest rozpoznawany przez odpowiedni automat ze stosem, rozważmy gramatykę bezkontekstową, w postaci normalnej Greibach i załóżmy, że słowo puste nie należy do języka generowanego przez tę gramatykę. Konstruujemy teraz automat ze stosem , który, jak udowodnimy, akceptuje poprzez pusty stos język . Niech

gdzie funkcja określona jest następujaco. Dla dowolnych

oraz równa jest zbiorowi pustemu we wszystkich pozostałych przypadkach.

A zatem jest to automat o jednym stanie , alfabetem wejściowym jest alfabet terminalny , alfabetem stosu jest suma mnogościowa alfabetu symboli nieterminalnych i terminalnych , a symbol początkowy stosu jest symbolem startowym gramatyki. Działanie automatu symuluje lewostronne wyprowadzenie w gramatyce

Dla dowolnego słowa istnieje lewostronne wyprowadzenie

gdzie , oraz , gdyż gramatyka jest w postaci Greibach. Odpowiada temu wyprowadzeniu następujące działanie automatu  :

A to oznacza zaakceptowanie słowa poprzez pusty stos. Zatem . Dla dowodu inkluzji w przeciwną stronę wykorzystamy implikację

która ma miejsce dla dowolnego . Implikację tę udowodnimy indukcyjnie ze względu na długość słowa . Dla słowa pustego oraz dla powyższa implikacja wynika bezpośrednio z definicji automatu ze stosem. Załóżmy teraz, że w i niech dla i . Mamy więc i w automacie . Z założenia indukcyjnego wnioskujemy, że w . W przypadku, gdy , wnioskujemy z określenia automatu ze stosem, że i wtedy w . Jeśli natomiast dla i , to w automacie ma miejsce wyprowadzenie

gdzie i i prawo . W dalszym ciągu działania automatu następuje krok , a to w konsekwencji oznacza, że w gramatyce ma miejsce wyprowadzenie

Załóżmy teraz, że automat rozpoznaje z pustym stosem język . Skonstruujemy gramatykę bezkontekstową , generującą ten sam język. Niech , gdzie . Do zbioru praw zaliczymy wyłącznie następujące prawa:

  1. dla wszystkich stanów ,
  2. dla dowolnych stanów jeśli ,
  3. jeśli .

Mamy więc następującą równoważność:

która w szczególności dla przyjmuje postać

i oznacza dla gramatyki wymazywanie symboli nieterminalnych, a dla automatu wymazywanie symboli stosu.

Skonstruowana gramatyka odtwarza działanie automatu działającego pod wpływem słowa wejściowego co udowodnimy poniżej. W tym celu wykażemy indukcyjnie ze względu na długość słowa następującą równoważność:

Dla równoważność redukuje się do obserwacji (2). Załóżmy teraz, że słowo oraz że w gramatyce mamy wyprowadzenie . Z postaci gramatyki wynika, że to wyprowadzenie można przedstawić nastepująco:

dla pewnego i odpowiednich .

Z założenia indukcyjnego wynika, iż pierwszy fragment wyprowadzenia jest w automacie zastąpiony równoważnie poprawnym obliczeniem

a drugi

A to oznacza, że w automacie mamy poprawne obliczenie

co kończy dowód indukcyjny równoważności. Na jej podstawie, przyjmując , otrzymujemy:

Uwzględniając, iż dla dowolnego stanu mamy w gramatyce prawo oraz że automat akceptuje słowa przez pusty stos (stan jest nieistotny), ostatnia równoważność kończy dowód twierdzenia.