Języki, automaty i obliczenia/Wykład 2: Gramatyka jako model obliczen. Hierarchia Chomsky'ego

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

W tym wykładzie wprowadzimy ogólne pojęcie systemu przepisującego, zdefiniujemy gramatykę, czyli szczególny typ systemu przepisującego oraz określimy cztery typy gramatyk wprowadzone przez Noama Chomsky'ego.

Kurt Goedel (1906-1978)
Zobacz biografię

Teoria języków formalnych i automatów tworzy i bada pewne modele obliczeń, można popularnie powiedzieć modele komputera, zwane automatami lub gramatykami. Jednym z głównych i ogólnych problemów wokół którego skupione są badania tej teorii jest problem możliwości i ograniczeń obliczeniowych. Początki tych rozważań sięgają lat trzydziestych ubiegłego stulecia i wiążą się z pracami K.Goedla i późniejszymi A.Turinga i A.Churcha. Równolegle do teorii automatów problematyka ta jest intensywnie badana w ramach teorii obliczalności i teorii złożoności.

W tym wykładzie wprowadzimy pierwszy z tych modeli, mianowicie gramatykę. Określimy także sposób wyprowadzenia (generowania) słowa zgodnie z regułami gramatycznymi i zdefiniujemy język opisywany przez gramatykę. Przedstawimy również podstawowe typy gramatyk wprowadzone do lingwistyki teoretycznej i później do teorii języków formalnych przez Noama Chomsky'ego, twórcę pojęcia gramatyki transformacyjno-generatywnej, co miało miejsce w roku 1957.

Alonso Church (1903-1995)
Zobacz biografię

Przez gramatykę rozumie się systematyczny opis wybranego języka naturalnego, opis, który obejmuje jego składnię (syntaktykę), znaczenie (semantykę) i fonologię, czyli dźwiękowy system języka. Reguły składni określają regularności rządzące kombinacjami słów, semantyka bada znaczenie słów i zdań, a fonologia wyróżnia dźwięki i ich dopuszczalne zestawienia w opisywanym języku.

Teoria języków formalnych bada wyłącznie syntaktyczne własności języków. Język rozumiany jest abstrakcyjnie, jako zbiór skończonych napisów. Zatem opierając się na wiadomościach z poprzedniego wykładu możemy powiedzieć, że język (formalny) to dowolny podzbiór wolnego monoidu . Baza tego wolnego monoidu, czyli zbiór to alfabet, a sam wolny monoid możemy interpretować, jako zbiór wszystkich możliwych napisów utworzonych w tym alfabecie. Na ogół język jest właściwym podzbiorem , czyli składa się z pewnych tylko ("poprawnych") napisów. Wyróżniając język zazwyczaj wprowadzamy pewne kryteria, które muszą spełniać napisy z tego języka. Dlatego o elementach języka mówimy, że spełniają te kryteria lub że są syntaktycznie poprawne.

Jak już powiedzieliśmy teoria języków formalnych tworzy pewne modele obliczeń lub inaczej systemy opisu języków zwane gramatykami i automatami. Od tych systemów żąda się, aby spełniały warunki efektywności analitycznej i efektywności syntetycznej. Pierwszy z warunków oznacza, że system opisu prowadzi do algorytmu, który w skończonej liczbie kroków rozstrzyga, czy dowolne słowo należy, czy też nie należy do tego języka. Spełnienie warunku drugiego daje w rezultacie algorytm, który umożliwia wygenerowanie wszystkich słów danego języka.

Emil Leon Post (1897-1954)
Zobacz biografię

Gramatyka to system, którego działanie opiera się na procesie sekwencyjnego przepisywania, czyli modyfikowania pewnych napisów (słów). Przepisywanie to realizowane jest poprzez reguły przyjęte w danym systemie jako dopuszczalne. Idea ta związana jest z nazwiskami takich logików jak Axel Thue czy Emil Post. W roku 1957 Noam Chomsky, lingwista amerykański, stworzył pewien matematyczny formalizm opisu języków naturalnych zwany gramatykami generacyjnymi.

Gramatyki te opisują wybrane, najbardziej istotne cechy syntaktyczne języków, w szczególności ich strukturalne regularności.

Idee Chomsky'ego bardzo szybko przeniknęły do innych dziedzin nauki. Stworzona teoria znalazła istotne zastosowanie w badaniach nad językami programowania. Z powodzeniem gramatyki Chomsky'ego służą również do budowania modeli procesów biologicznych, czy też procesów badanych przez nauki o społeczeństwie. Teoria gramatyk rozwinęła się w wielu kierunkach, służąc jako formalny opis sekwencyjnych zmian różnorakich obiektów, takich jak, termy, grafy, obrazy, czy fraktale.

System przepisujący

Definicja 1.1

System przepisujący jest to para , gdzie
jest dowolnym skończonym zbiorem (alfabetem),
- skończoną relacją (zbiorem praw).

Fakt, że para zapisujemy, i nazywamy prawem przepisywania lub produkcją w systemie .

Definicja 1.2

Niech będzie dowolnym systemem przepisującym, a dowolnymi słowami.

System przepisuje słowo na słowo (generuje z ) bezpośrednio, co oznacza się symbolem
,

jeśli istnieją słowa oraz prawo takie, że

System przepisuje słowo na słowo (generuje z ), co oznacza się symbolem
,
jeśli istnieją słowa oraz takie, że

Bezpośrednie wyprowadzenie jest relacją na wolnym monoidzie , a wyprowadzenie zwrotnym i przechodnim domknięciem tej relacji.

Ciąg nazywamy wyprowadzeniem lub wywodem w systemie . Liczba określa długość wyprowadzenia. Wyprowadzenie oznacza się także następująco:

Przykład 1.1

Niech będzie systemem przepisującym. W systemie słowo można wyprowadzić ze słowa (rysunek 1).

Rozważa się systemy przepisujące generujące lub rozpoznające język.

Definicja 1.3

Niech będzie dowolnym systemem przepisującym, a dowolnym, ustalonym podzbiorem .

  • językiem generowanym przez nazywamy zbiór
,
  • językiem rozpoznawanym przez nazywamy zbiór:
,

Przykład 1.2

Jeśli w przykładzie 1.1 (patrz przykład 1.1.) przyjmiemy to


Axel Thue (1863-1922)
Zobacz biografię

Gramatyka, której definicję teraz wprowadzimy, jest szczególnym systemem Thuego. Można powiedzieć, że jest to system Thuego tak określony, aby poprzez wskazanie jedynie poprawnych sposobów generowania napisów definiować język. Gramatyka to jedno z najważniejszych pojęć teorii języków formalnych. Używany poniżej, dla i , symbol oznacza liczbę wystąpień liter z alfabetu w słowie .

Definicja 1.4

Gramatyka jest to system , w którym

- skończony zbiór symboli nieterminalnych (alfabet nieterminalny),

- skończony zbiór symboli terminalnych (alfabet terminalny),

- skończona relacja, zbiór produkcji (praw),

- symbol początkowy (startowy).

Ponadto zakładamy, że i dla każdego .

A zatem w gramatyce alfabety terminalny i nieterminalny są rozłącznymi zbiorami, a słowo występujące po lewej stronie produkcji zawiera co najmniej jeden symbol nieterminalny. Fakt, że para zapisujemy:

Wykorzystujemy też zdefiniowane dla systemów przepisujących pojęcia generowania bezpośredniego i generowania .

Definicja 1.5

Językiem generowanym przez gramatykę nazywamy zbiór:

Łatwo zauważyć, że pomiędzy językiem a generującą go gramatyką nie ma odpowiedniości wzajemnie jednoznacznej. Dany język może być generowany przez wiele gramatyk, czasem o bardzo różnej strukturze i własnościach. Stąd potrzeba wprowadzenia pojęcia równoważności językowej dla gramatyk.

Definicja 1.6

Gramatyki i równoważne (językowo) wtedy i tylko wtedy, gdy .

Przykład 1.3

(1) Gramatyka , w której generuje język
.
(2) Gramatyka , w której generuje język
.
(3) Gramatyka , w której ,
generuje język
(4) Gramatyka , w której ,
generuje język

Gramatyki i są równoważne. Równoważne również są gramatyki i .

Klasyfikacja Chomsky'ego

Wprowadzimy teraz cztery typy gramatyk określonych, jak powiedziano już wcześniej, przez Noama Chomsky'ego.

Definicja 2.1

Gramatyka jest typu dla wtedy i tylko wtedy, gdy spełnia następujące warunki:

typ(0): każda gramatyka, czyli system spełniajacy definicję 1.4 (patrz definicja 1.4.)
typ(1): kontekstowa, czyli gramatyka, w której każde prawo ze zbioru ma postać
gdzie lub
przy czym, jeśli , to nie występuje po prawej stronie w żadnym prawie z ,
typ (2): bezkontekstowa, czyli gramatyka, w której każde prawo ze zbioru ma postać
gdzie ,
typ (3): regularna, czyli gramatyka, w której każde prawo ze zbioru ma postać
gdzie .

Przykład 2.1

Gramatyki z przykładu 1.3 (patrz przykład 1.3.) są odpowiednio

(1) - typu (3)
(2) - typu (2)
(3) - typu (1)
(4) - typu (0)

Natomiast język jest typu (3),
język jest typu (1).

W oparciu o wprowadzone typy gramatyk określamy odpowiadające im rodziny (klasy) języków, oznaczając przez

: - rodzinę wszystkich języków typu 0,
: - rodzinę wszystkich języków typu 1, czyli języków kontekstowych,
: - rodzinę wszystkich języków typu 2, czyli języków bezkontekstowych,
: - rodzinę wszystkich języków typu 3, czyli języków regularnych.

Pomiędzy wprowadzonymi rodzinami języków zachodzą następujące zależności:

Inkluzje pierwsza i trzecia wynikają bezpośrednio z definicji odpowiednich klas języków, a więc z definicji gramatyk regularnej i bezkontekstowej oraz kontekstowej i typu (0). Natomiast fakt, że udowodnimy później. Podobnie z dalszych rozważań wynika, że powyższe inkluzje są właściwe.

Noam Avram Chomsky (1928-)
Zobacz biografię

Gramatyki spełniają warunek efektywności syntetycznej. Systemami, które realizują warunek efektywności analitycznej, są automaty. Automaty działają w ten sposób, iż pod wpływem zewnętrznego sygnału zmieniają swój stan. W efekcie tej zmiany rozpoznają bądź nie ciągi takich sygnałów reprezentowane przez słowa. Zatem działanie automatu polega na testowaniu kolejno słów z i określaniu, które z nich są rozpoznawane (spełniają określone kryteria), a które nie są rozpoznawane. Ogół słów rozpoznanych przez automat tworzy język rozpoznawany przez ten automat. Dla każdej z określonych powyżej rodzin języków, w sensie Chomsky'ego określa się odpowiadającą jej rodzinę automatów.

Język jest typu (i) dla wtedy i tylko wtedy, gdy jest rozpoznawany przez jakiś automat z odpowiedniej rodziny. Definicje automatów i ich własności wprowadzane będą sukcesywnie przy prezentowaniu poszczególnych rodzin języków.