Hierarchia Chomskiego

W teorii języka formalnego , informatyce i językoznawstwie hierarchia Chomsky'ego jest hierarchią obejmującą klasy gramatyk formalnych . Ta hierarchia gramatyk została opisana przez Noama Chomsky'ego w 1956 roku.

Gramatyki formalne

Główny artykuł: Gramatyka formalna

Gramatyka formalna tego typu składa się ze skończonego zbioru reguł produkcji ( lewa strona → prawa strona ), gdzie każda strona składa się ze skończonego ciągu następujących symboli:

• skończony zestaw nieterminalnych symboli (wskazujących, że można jeszcze zastosować jakąś regułę produkcji)
• skończony zestaw symboli końcowych (wskazujących, że nie można zastosować żadnej reguły produkcji)
• symbol startu ( wyróżniony symbol nieterminalny)

Gramatyka formalna dostarcza schematu aksjomatów (lub generuje ) dla języka formalnego , który jest (zwykle nieskończonym) zbiorem sekwencji symboli o skończonej długości , które można zbudować, stosując reguły produkcji do innej sekwencji symboli (która początkowo zawiera tylko symbol startu). Regułę można zastosować, zastępując występowanie symboli po jej lewej stronie tymi, które pojawiają się po jej prawej stronie. Sekwencja zastosowań reguł nazywana jest pochodną . Taka gramatyka definiuje język formalny: wszystkie słowa składające się wyłącznie z symboli końcowych, do których można dojść przez wyprowadzenie z symbolu początkowego.

wielkie litery, terminale przez małe litery, a symbol startu przez S. Na przykład gramatyka z terminalami { a, b } , nieterminalami { S, A, B } , regułami produkcji

S → AB

S → ε (gdzie ε jest łańcuchem pustym)

A → aS

B → b

i symbol startu S , definiuje język wszystkich słów postaci $a,$ n kopii po których n kopii b ) .

Poniżej znajduje się prostsza gramatyka, która definiuje ten sam język:

Zaciski { a, b } , Nieterminale { S } , Symbol startu S , Reguły produkcji

S → aSb

S → ε

Jako inny przykład gramatykę dla podzbioru zabawek języka angielskiego przedstawia wzór:

terminale

{generate, hate, great, green, idee, lingwiści}

nieterminale

{ S, NP, VP, N, V, Adj }

reguły produkcji

S → NP VP

NP → Adj NP

NP → N

VP → V NP

VP → V

N → pomysły

N → lingwiści

V → generować

V → nienawidzić

Przym. → wielki

Przym. → zielony

i symbol startu S . Przykładem jest wyprowadzenie

S → NP VP → Adj NP VP → Adj N VP → Adj NV NP → Adj NV Adj NP → Adj NV Adj Adj NP → Adj NV Adj Adj N → wielki NV Adj Adj N → wielcy lingwiści V Adj Adj N → wielcy lingwiści generują Adj Adj N → świetni lingwiści generują świetne Adj N → świetni lingwiści generują świetne zielone N → świetni lingwiści generują świetne zielone pomysły.

Inne sekwencje, które można wyprowadzić z tej gramatyki, to: „ idee nienawidzą wielkich lingwistów ” oraz „ idee generują ”. Chociaż te zdania są bezsensowne, są poprawne składniowo. zdania niepoprawnego składniowo (np. „ idee, idee, wielka nienawiść ”). Zobacz „ Bezbarwne zielone idee śpią wściekle ”, aby zapoznać się z podobnym przykładem podanym przez Chomsky'ego w 1957 roku; zobacz Gramatyka struktury fraz i Zasady struktury fraz , aby zapoznać się z bardziej naturalnymi przykładami języka i problemami gramatyki formalnej w tej dziedzinie.

Hierarchia

Zestawy inkluzji opisane hierarchią Chomsky'ego

Poniższa tabela podsumowuje każdy z czterech typów gramatyk Chomsky'ego, klasę języka, który generuje, typ automatu, który go rozpoznaje, oraz formę, jaką muszą mieć jego reguły.

Gramatyka	Języki	Automat	Zasady produkcji (ograniczenia)*	Przykłady
Wpisz-0	Rekurencyjnie przeliczalny	Maszyna Turinga	${\ Displaystyle \ gamma \ rightarrow \ alfa}$ ( ${\ Displaystyle \ gamma}$ niepuste)	${\ displaystyle L = \ {w | w}$ opisuje kończącą maszynę Turinga ${\ displaystyle \}}$
Typ 1	Kontekstowe	Niedeterministyczna maszyna Turinga z ograniczeniami liniowymi	${\ Displaystyle \ alfa A \ beta \ strzałka w prawo \ alfa \ gamma \ beta}$	${\ Displaystyle L = \ {a ^ {n} b ^ {n} c ^ {n} | n> 0 \}}$
Typ-2	Bezkontekstowe	Niedeterministyczny automat przesuwający w dół	${\ Displaystyle A \ strzałka w prawo \ alfa}$	${\ Displaystyle L = \ {a ^ {n} b ^ {n} | n> 0 \}}$
Typ-3	Regularny	Automat skończony	${\ Displaystyle A \ rightarrow {\ tekst {a}}}$ i ${\ Displaystyle A \ rightarrow {\ tekst {a}} B}$	${\ Displaystyle L = \ {a ^ {n} | n \ geq 0 \}}$
* Znaczenie symboli: ${\ Displaystyle {\ tekst {a}}}$ = terminal ${\ Displaystyle A}$ , ${\ Displaystyle B}$ = nieterminalne ${\ Displaystyle \ alpha}$ , ${\ Displaystyle \ beta}$ , ${\ Displaystyle \ gamma}$ = ciąg terminali i / lub nieterminali

Zauważ, że zbiór gramatyk odpowiadający językom rekurencyjnym nie należy do tej hierarchii; byłyby one odpowiednio między typem 0 a typem 1.

Każdy język regularny jest bezkontekstowy, każdy język bezkontekstowy jest kontekstowy, każdy język kontekstowy jest rekurencyjny, a każdy język rekurencyjny jest rekurencyjnie przeliczalny. To wszystko są właściwe inkluzje, co oznacza, że ​​istnieją rekurencyjnie wyliczalne języki, które nie są kontekstowe, języki kontekstowe, które nie są bezkontekstowe i języki bezkontekstowe, które nie są regularne.

Gramatyki typu 0

Główny artykuł: gramatyka nieograniczona

Gramatyki typu 0 obejmują wszystkie gramatyki formalne. Generują dokładnie wszystkie języki, które może rozpoznać maszyna Turinga . Języki te są również znane jako języki rekurencyjnie przeliczalne lub języki rozpoznawalne przez Turinga . Zauważ, że różni się to od języków rekurencyjnych , o których może decydować zawsze zatrzymująca się maszyna Turinga .

Gramatyki typu 1

Główny artykuł: gramatyka kontekstowa

Gramatyki typu 1 generują języki kontekstowe . Te gramatyki mają reguły postaci ${\ Displaystyle \ alfa A \ beta \ rightarrow \ alfa \$$gamma$${\ displaystyle \ beta}$ beta $}$ z i $terminali$ ciągi i / lub nieterminali. Łańcuchy i mogą $niepuste$$puste$ , ale $muszą$ Reguła $,$$dozwolona$ ​​jeśli stronie żadnej reguły. Języki opisane przez te gramatyki są dokładnie wszystkimi językami, które mogą być rozpoznane przez automat o liniowych ograniczeniach (niedeterministyczna maszyna Turinga, której taśma jest ograniczona przez stałą razy długość wejścia).

Gramatyki typu 2

Główny artykuł: Gramatyka bezkontekstowa

Gramatyki typu 2 generują języki bezkontekstowe . $Są$$jest$ zdefiniowane przez reguły w postaci, $gdzie$ nieterminalem , a terminali i / lub Te języki to dokładnie wszystkie języki, które mogą być rozpoznawane przez niedeterministyczny automat przesuwający w dół . Języki bezkontekstowe — a raczej ich podzbiór deterministycznych języków bezkontekstowych — są teoretyczną podstawą struktury fraz większości języków programowania , chociaż ich składnia obejmuje również kontekstowe rozpoznawanie nazw ze względu na deklaracje i zakres . Często używany jest podzbiór gramatyk, aby ułatwić parsowanie, na przykład przez parser LL .

Gramatyki typu 3

Główny artykuł: Gramatyka regularna

Gramatyki typu 3 generują języki regularne . Taka gramatyka ogranicza swoje reguły do ​​pojedynczego nieterminala po lewej stronie i prawej strony składającej się z jednego terminala, po którym prawdopodobnie następuje pojedynczy nieterminal (prawy regularny). Alternatywnie, prawa strona gramatyki może składać się z pojedynczego terminala, ewentualnie poprzedzonego pojedynczym nieterminalem (lewy regularny). Generują one te same języki. Jeśli jednak połączone zostaną reguły lewostronne i reguły regularne prawicowe, język nie musi już być regularny. Reguła $dozwolona$$,$ ​​​​jeśli nie stronie żadnej reguły Te języki to dokładnie wszystkie języki, które mogą być rozstrzygnięte przez automat skończony . Dodatkowo tę rodzinę języków formalnych można uzyskać za pomocą wyrażeń regularnych . Języki regularne są powszechnie używane do definiowania wzorców wyszukiwania i struktury leksykalnej języków programowania.

• Chomsky, Noam (1959). „O pewnych formalnych właściwościach gramatyk” (PDF) . Informacji i Kontroli . 2 (2): 137–167. doi : 10.1016/S0019-9958(59)90362-6 .
• Chomsky, Noam ; Schützenberger, Marcel P. (1963). „Algebraiczna teoria języków bezkontekstowych”. W Braffort, P.; Hirschberg, D. (red.). Programowanie komputerowe i systemy formalne (PDF) . Amsterdam: Północna Holandia. s. 118–161. Zarchiwizowane (PDF) od oryginału w dniu 13.06.2011 r.
•   Davis, Martin D.; Sigal, Ron; Weyuker, Elaine J. (1994). Obliczalność, złożoność i języki: podstawy informatyki teoretycznej (wyd. 2). Boston: Academic Press, Harcourt, Brace. P. 327 . ISBN 0-12-206382-1 .