Hierarchia Chomsky’ego i gramatyka normatywna (1956)

Hierarchia Chomsky’ego to klasyfikacja gramatyk formalnych — oraz języków, które te gramatyki generują — na cztery zagnieżdżone poziomy, od typu 0 (gramatyki nieograniczone) do typu 3 (gramatyki regularne), uporządkowane według mocy generatywnej. Wprowadził ją Noam Chomsky w pracy „Three models for the description of language” z 1956 roku, a ścisłą postać matematyczną nadał jej w 1959 roku w artykule „On Certain Formal Properties of Grammars”. Każdemu poziomowi hierarchii odpowiada klasa abstrakcyjnych maszyn (automatów), które rozpoznają dokładnie języki tego poziomu — dzięki temu hierarchia stała się fundamentem zarówno językoznawstwa teoretycznego, jak i informatyki.

W tym ujęciu język rozumiany jest jako zbiór (skończony lub nieskończony) zdań, z których każde ma skończoną długość i jest zbudowane ze skończonego zestawu elementów. Gramatyka to skończony zbiór reguł przepisywania, który generuje dokładnie zdania danego języka — ani mniej, ani więcej. Cztery typy różnią się wyłącznie tym, na ile swobody pozwalają tym regułom.

Cztery typy gramatyk

Hierarchia jest ściśle zagnieżdżona: każdy język regularny jest bezkontekstowy, każdy bezkontekstowy — kontekstowy, a każdy kontekstowy — rekurencyjnie przeliczalny. W drugą stronę żadna z tych zależności nie działa.

Typ 0 — gramatyki nieograniczone: reguły produkcji nie podlegają żadnym ograniczeniom. Generują języki rekurencyjnie przeliczalne — wszystko to, co potrafi rozpoznać maszyna Turinga. To najbardziej zewnętrzna i najpotężniejsza klasa; w ogólnym przypadku nie istnieje procedura rozstrzygająca, czy dowolny napis należy do języka typu 0.
Typ 1 — gramatyki kontekstowe: reguła może przepisać symbol tylko w określonym kontekście, a prawa strona reguły nigdy nie może być krótsza od lewej. Generują języki kontekstowe, rozpoznawane przez automaty liniowo ograniczone — maszyny Turinga, których taśma robocza jest ograniczona do długości wejścia. Podręcznikowy przykład to język aⁿbⁿcⁿ: jednakowa liczba symboli a, b i c, w tej kolejności.
Typ 2 — gramatyki bezkontekstowe: każda reguła przepisuje pojedynczy symbol niezależnie od otoczenia. Generują języki bezkontekstowe, rozpoznawane przez automaty ze stosem. Podręcznikowy przykład to aⁿbⁿ albo język poprawnie sparowanych nawiasów. Składnia większości języków programowania jest zdefiniowana właśnie gramatykami bezkontekstowymi.
Typ 3 — gramatyki regularne: klasa najbardziej ograniczona — reguła może wyprodukować co najwyżej jeden symbol końcowy i co najwyżej jeden symbol pomocniczy. Generują języki regularne, rozpoznawane przez automaty skończone i opisywane wyrażeniami regularnymi, np. „wszystkie napisy złożone z a i b, które kończą się na b”.

Rok 1956: skąd wzięła się hierarchia

Na początku lat 50. dominujący matematyczny model języka pochodził z teorii informacji: zdanie traktowano jako wynik procesu Markowa, który dobiera każde kolejne słowo na podstawie słów bezpośrednio je poprzedzających. Był to model skończenie stanowy i probabilistyczny, dobrze współgrający z psychologią behawiorystyczną. Praca Chomsky’ego z 1956 roku („Three models for the description of language”, IRE Transactions on Information Theory) porównywała trzy kandydujące modele: model skończenie stanowy, gramatyki struktur frazowych i gramatykę transformacyjną.

Kluczowy był wynik negatywny: języka angielskiego nie da się adekwatnie opisać modelem skończenie stanowym, ponieważ dopuszcza on nieograniczone zagnieżdżanie zależności — konstrukcje typu „jeżeli… to” czy „albo… albo” można w sobie osadzać dowolnie głęboko, a urządzenie skończenie stanowe nie ma pamięci, by śledzić poziomy zagnieżdżenia. Rok później książka Syntactic Structures (1957) spopularyzowała ten argument, a artykuł z 1959 roku zdefiniował pełną, czteropoziomową hierarchię z matematyczną precyzją. Hierarchia szybko stała się fundamentem budowy kompilatorów i teorii obliczeń — i to jest, jak dotąd, jej najtrwalsze praktyczne dziedzictwo.

Gdzie w hierarchii mieszczą się języki naturalne?

Wbrew popularnemu uproszczeniu Chomsky nie twierdził, że udowodnił przynależność języków ludzkich do konkretnego poziomu. Jego wynik z 1956 roku był negatywny: języki naturalne nie są regularne (nie są typu 3). Pytanie, czy są bezkontekstowe (typu 2), pozostawało otwarte przez trzy dekady — dopiero w 1985 roku Stuart Shieber wykazał, na przykładzie krzyżujących się zależności czasownikowych w szwajcarskiej odmianie niemieckiego, że co najmniej jeden język naturalny dowodnie nie jest bezkontekstowy.

Dzisiejszy konsensus, sięgający prac Aravinda Joshiego, głosi, że języki naturalne są łagodnie kontekstowe (mildly context-sensitive): nieco powyżej typu 2, ale daleko poniżej pełnej mocy typu 1, o typie 0 nie wspominając. Dla Chomsky’ego aparat formalny służył szerszej tezie: skoro każde dziecko opanowuje tak złożony system bez jawnej instrukcji, zdolność do gramatyki musi być częścią naszego biologicznego wyposażenia — to teza gramatyki uniwersalnej i urządzenia do akwizycji języka, rozwinięta w jego natywistycznej teorii języka.

Gramatyka generatywna a gramatyka normatywna

„Gramatyka” to jedno z najbardziej wieloznacznych słów w nauce języków — i hierarchia pomaga je rozplątać. W sensie Chomsky’ego gramatyka to formalne urządzenie, które generuje język: coś jak linia montażowa produkująca ciągi symboli. Opisuje ona, które zdania są możliwe, i nie mówi nic o tym, które są „poprawne”.

Gramatyka normatywna (preskryptywna) to coś zupełnie innego: zbiór społecznych konwencji dyktujących, jak języka należy używać, zwłaszcza w piśmie i w sytuacjach oficjalnych — normy poprawności dotyczące słownictwa, składni, ortografii i interpunkcji. Kodyfikują ją instytucje, słowniki poprawnościowe i programy szkolne; zmienia się wraz z autorytetami i modą, a nie na mocy dowodu matematycznego.

Pomiędzy nimi mieści się gramatyka, którą rodzimi użytkownicy faktycznie noszą w głowach: niejawny, zinternalizowany system — Chomsky nazywa go kompetencją — dzięki któremu mówiący natychmiast czuje, że zdanie brzmi dobrze albo źle, nawet jeśli nie potrafi podać ani jednej reguły. Gramatyka generatywna jest jawnym, naukowym modelem tej nieuświadomionej wiedzy. Więcej o tym rozróżnieniu piszemy w haśle co to jest gramatyka języka.

Co z tego wynika dla nauki języka

Gramatyka, na której uczącemu się naprawdę zależy, to nie normatywny zbiór przepisów, lecz intuicja rodzimego użytkownika: zinternalizowany system, który automatycznie produkuje i ocenia zdania. Taki system przyswaja się implicite, przetwarzając dużą liczbę sensownych zdań, a nie wkuwając reguły preskryptywne — dlatego prace Chomsky’ego przeobraziły dydaktykę języków, przesuwając jej cel z drylowania reguł na budowanie kompetencji. Metody oparte na całych zdaniach i systematycznych powtórkach, takie jak metoda Taalhammera, wynikają wprost z tego spostrzeżenia: karmimy wewnętrzną gramatykę przykładami tak długo, aż sama zacznie generować.

Najczęściej zadawane pytania

Czym jest hierarchia Chomsky’ego w prostych słowach?

To ranking gramatyk według ich mocy. Gramatyki typu 3 (regularne) radzą sobie tylko z prostymi wzorcami; typu 2 (bezkontekstowe) — z zagnieżdżaniem, jak nawiasy w nawiasach; typu 1 (kontekstowe) potrafią uzgadniać kilka liczności naraz; typ 0 opisuje wszystko, co w ogóle daje się obliczyć. Każdy poziom zawiera w sobie wszystkie poziomy niższe.

Dlaczego hierarchia Chomsky’ego jest ważna w informatyce?

Bo każdemu poziomowi odpowiada model maszyny: wyrażenia regularne i analizatory leksykalne żyją na poziomie typu 3, parsery języków programowania — typu 2, a teoria obliczalności — typu 0. Hierarchia mówi inżynierom, które narzędzie wystarcza do którego zadania; używa się jej do dziś, m.in. do badania, co potrafią, a czego nie potrafią obliczyć neuronowe modele językowe.

Czy hierarchia dowiodła, że język jest wrodzony?

Nie. Hierarchia jest neutralnym narzędziem matematycznym. Argument Chomsky’ego o wrodzoności opiera się na ubóstwie bodźca — dzieci przyswajają bogatą gramatykę na podstawie ograniczonych danych — a hierarchia dostarczyła mu formalnego tła, pokazując, jak dużo struktury musi zawierać każda adekwatna gramatyka języka ludzkiego.

Źródła

Noam Chomsky, „Three models for the description of language”, IRE Transactions on Information Theory 2(3), 1956.
Noam Chomsky, „On Certain Formal Properties of Grammars”, Information and Control 2(2), 1959.
Noam Chomsky, Syntactic Structures, Mouton, 1957.
Stuart M. Shieber, „Evidence Against the Context-Freeness of Natural Language”, Linguistics and Philosophy 8, 1985.
Aravind K. Joshi, „Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural descriptions?”, w: Natural Language Parsing, Cambridge University Press, 1985.
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, wyd. 3, Pearson, 2006.