Hierarchia Chomskiego - Chomsky hierarchy

W formalnej teorii języków , informatyki i lingwistyki The hierarchia Chomsky'ego (czasami określane jako hierarchii Chomsky-Schützenberger ) jest hierarchia powstrzymywanie klas formalnych gramatyk .

Ta hierarchia gramatyk została opisana przez Noama Chomsky'ego w 1956 roku. Jej nazwa pochodzi również od Marcela-Paula Schützenbergera , który odegrał kluczową rolę w rozwoju teorii języków formalnych .

Gramatyki formalne

Formalna gramatyka 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 zbiór nieterminalnych symboli (wskazujący, że jakaś reguła produkcji może być jeszcze zastosowana)
• skończony zestaw symboli końcowych (wskazujący, że nie można zastosować żadnej reguły produkcji)
• symbolu startu (wybitnym nieterminalowi Symbol)

Formalnej gramatyki stanowi schemat aksjomatu (albo generuje ) do formalnego języka , który jest (zazwyczaj nieskończony) zbiór sekwencji skończonej długości symboli , które mogą być wykonane przy zastosowaniu zasad produkcji na inną sekwencję symboli (która początkowo zawiera tylko symbol startu). Reguła może być zastosowana poprzez zastąpienie występowania symboli po jej lewej stronie tymi, które pojawiają się po jej prawej stronie. Sekwencja aplikacji reguł nazywana jest derywacją . 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ść poprzez wyprowadzenie z symbolu początkowego.

Nieterminale są często reprezentowane przez wielkie litery, terminale przez małe litery, a symbol początkowy przez S . Na przykład gramatyka z terminalami { a, b } , nieterminalami { S, A, B } , reguły produkcji

S → AB

S → ε (gdzie ε jest pustym ciągiem)

A → aS

B → b

i symbol początkowy S , określa język wszystkich słów postaci (tj. n kopii a następuje n kopii b ). ${\ Displaystyle a ^ {n} b ^ {n}}$

Poniżej przedstawiono prostszą gramatykę, która definiuje ten sam język:

Terminale { a, b } , nieterminale { S } , symbol startu S , reguły produkcji

S → aSb

S → ε

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

terminale

{generowanie, nienawiść, świetne, zielone, pomysły, językoznawcy}

nieterminale

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

zasady produkcji

S → NP VP

NP → Adj NP

NP → N

VP → V NP

VP → V

N → pomysły

N → językoznawcy

V → generuj

V → nienawiść

Przym → wielki

Przym → zielony

i symbol startu S . Przykładowe wyprowadzenie to

S → NP VP → Adj NP VP → Adj N VP → Adj NV Adj NP → Adj NV Adj NP → Adj NV Adj Adj NP → Adj NV Adj Adj N → świetny NV Adj Adj N → świetni lingwiści V Adj Adj N → świetni lingwiści generują Przym Przym N → świetni lingwiści generują świetne Przym 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 ” i „ pomysły generują ”. Chociaż te zdania są bezsensowne, są poprawne składniowo. Z tej gramatyki nie można wyprowadzić zdania niepoprawnego składniowo (np. „ pomysły nienawidzą wielkich pomysłów ”). Zobacz „ Bezbarwne zielone idee śpią wściekle ” dla podobnego przykładu podanego przez Chomsky'ego w 1957 roku; Zobacz Gramatyka struktury fraz i Reguły struktury fraz, aby zapoznać się z bardziej naturalnymi przykładami języka i problemami gramatyki formalnej w tym obszarze.

Hierarchia

Zestaw inkluzji opisanych przez 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
Typ-0	Rekurencyjnie przeliczalne	Maszyna Turinga	${\ Displaystyle \ gamma \ rightarrow \ alfa}$ (bez ograniczeń)	${\ Displaystyle L = \ {w | w}$ opisuje kończącą maszynę Turinga${\ Displaystyle \}}$
Typ 1	Kontekstowe	Niedeterministyczna maszyna Turinga z ograniczeniem liniowym	${\ Displaystyle \ alfa A \ beta \ rightarrow \ alfa \ gamma \ beta}$	${\ Displaystyle L = \ {a ^ {n} b ^ {n} c ^ {n} | n> 0 \}}$
Typ-2	Bez kontekstu	Zakaz deterministyczny automat ze stosem	${\displaystyle A\rightarrow \alfa}$	${\ Displaystyle L = \ {a ^ {n} b ^ {n} | n> 0 \}}$
Typ-3	Regularny	Automat skończony	${\displaystyle A\rightarrow {\tekst{a}}}$ oraz ${\ Displaystyle A \ rightarrow {\ tekst {a}} B}$	${\ Displaystyle L = \ {a ^ {n} | n \ geq 0 \}}$
* Znaczenie symboli: ${\displaystyle {\tekst{a}}}$ = terminal ${\ Displaystyle A}$, = nieterminal${\ Displaystyle B}$ ${\ Displaystyle \ alfa}$, , = ciąg terminali i/lub nieterminali${\ Displaystyle \ beta}$${\ Displaystyle \ gamma}$ ${\ Displaystyle \ alfa}$, = może pusty${\ Displaystyle \ beta}$ ${\ Displaystyle \ gamma}$ = nigdy nie pusty

Zauważ, że zbiór gramatyk odpowiadający językom rekurencyjnym nie jest członkiem 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. Są to wszystkie właściwe inkluzje, co oznacza, że ​​istnieją języki rekurencyjnie przeliczalne, które nie są kontekstowe, języki kontekstowe, które nie są bezkontekstowe, oraz języki bezkontekstowe, które nie są regularne.

Gramatyki typu 0

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 rozpoznawane przez Turinga . Zauważ, że ten różni się od języków rekurencyjnych , które mogą być zdecydowały przez zawsze powstrzymania maszyny Turinga .

Gramatyki typu 1

Gramatyki typu 1 generują języki kontekstowe . Te gramatyki mają reguły postaci z nieterminalami i , oraz ciągami terminali i/lub nieterminali. Ciągi i mogą być puste, ale nie mogą być puste . Reguła jest dozwolona, ​​jeśli nie pojawia się po prawej stronie żadnej reguły. Języki opisane przez te gramatyki to dokładnie wszystkie języki, które mogą być rozpoznane przez automat liniowo ograniczony (niedeterministyczną maszynę Turinga, której taśma jest ograniczona stałą pomnożoną przez długość wejścia). ${\ Displaystyle \ alfa A \ beta \ rightarrow \ alfa \ gamma \ beta}$${\ Displaystyle A}$${\ Displaystyle \ alfa}$${\ Displaystyle \ beta}$${\ Displaystyle \ gamma}$${\ Displaystyle \ alfa}$${\ Displaystyle \ beta}$${\ Displaystyle \ gamma}$${\displaystyle S\rightarrow \epsilon}$${\displaystyle S}$

Gramatyki typu 2

Języki bezkontekstowe generują gramatyki typu 2 . Są one zdefiniowane przez reguły postaci z byciem nieterminalem i będącym ciągiem terminali i/lub nieterminali. Te języki to dokładnie wszystkie języki, które mogą być rozpoznane przez niedeterministyczny automat ze zsuwaniem . Języki bezkontekstowe — a raczej jego podzbiór deterministycznego języka bezkontekstowego — stanowią teoretyczną podstawę struktury fraz większości języków programowania , chociaż ich składnia obejmuje również kontekstowe rozwiązywanie nazw ze względu na deklaracje i zakres . Często podzbiór gramatyk jest używany, aby ułatwić parsowanie, na przykład przez parser LL . ${\displaystyle A\rightarrow \alfa}$${\ Displaystyle A}$${\ Displaystyle \ alfa}$

Gramatyki typu 3

Gramatyki typu 3 generują języki regularne . Taka gramatyka ogranicza swoje reguły do ​​jednego nieterminala po lewej stronie i prawej strony składającej się z jednego terminala, po którym może następować pojedynczy nieterminal (prawy regularny). Alternatywnie, prawa strona gramatyki może składać się z jednego terminala, ewentualnie poprzedzonego pojedynczym nieterminalem (lewy regularny). Generują one te same języki. Jednakże, jeśli połączy się reguły lewostronne i praworegularne, język nie musi być już regularny. Reguła jest również dozwolona tutaj, jeśli nie pojawia się po prawej stronie żadnej reguły. Języki te są dokładnie wszystkimi językami, które mogą być określone 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. ${\displaystyle S\rightarrow \varepsilon}$${\displaystyle S}$

Bibliografia

• Chomsky, Noam (1959). „O pewnych formalnych właściwościach gramatyk” (PDF) . Informacja i kontrola . 2 (2): 137–167. doi : 10.1016/S0019-9958(59)90362-6 .
• Chomsky, Noam ; Schützenberger, Marcel P. (1963). „Teoria algebraiczna języków bezkontekstowych”. W Braffort, P.; Hirschberg, D. (red.). Programowanie komputerowe i systemy formalne (PDF) . Amsterdam: Holandia Północna. s. 118–161.
• Davis, Martin D.; Sigal, Ron; Weyuker, Elaine J. (1994). Obliczalność, złożoność i języki: podstawy informatyki teoretycznej (2nd ed.). Boston: prasa akademicka, Harcourt, Brace. P. 327 . Numer ISBN 0-12-206382-1.