Chomského hierarchie - Chomsky hierarchy

v teorie formálního jazyka, počítačová věda a lingvistika, Chomského hierarchie (příležitostně označované jako Chomsky – Schützenbergerova hierarchie)^[1] je hierarchie omezení tříd formální gramatiky.

Tuto hierarchii gramatik popsal Noam Chomsky v roce 1956.^[2] Je také pojmenována po Marcel-Paul Schützenberger, který sehrál zásadní roli ve vývoji teorie formální jazyky.

Formální gramatiky

Formální gramatika tohoto typu se skládá z konečné množiny výrobní pravidla (levá strana → pravá strana), kde každá strana sestává z konečné posloupnosti následujících symbolů:

• konečná sada neterminální symboly (což naznačuje, že některé produkční pravidlo lze ještě použít)
• konečná sada koncové symboly (což naznačuje, že nelze použít žádné produkční pravidlo)
• A počáteční symbol (výrazný neterminální symbol)

A formální gramatika poskytuje schéma axiomu pro (nebo generuje) a formální jazyk, což je (obvykle nekonečná) sada posloupnosti symbolů konečné délky které mohou být vytvořeny použitím výrobní pravidla k další posloupnosti symbolů (která zpočátku obsahuje pouze počáteční symbol). Pravidlo lze použít nahrazením výskytu symbolů na levé straně symboly, které se objevují na pravé straně. Sekvence aplikací pravidel se nazývá a derivace. Taková gramatika definuje formální jazyk: všechna slova skládající se pouze z terminálních symbolů, kterých lze dosáhnout odvozením od počátečního symbolu.

Nonterminály jsou často reprezentovány velkými písmeny, terminály malými písmeny a počáteční symbol pomocí S. Například gramatika s terminály {a, b}, neterminály {S, A, B}, výrobní pravidla

S → AB

S → ε (kde ε je prázdný řetězec)

A → tak jako

B → b

a začátek symbolu S, definuje jazyk všech slov formuláře ${displaystyle a ^ {n} b ^ {n}}$ (tj. n kopie A následován n kopie b).

Následuje jednodušší gramatika, která definuje stejný jazyk:

Terminály {a, b}, Neterminálové {S}, Start symbol S, Pravidla výroby

S → aSb

S → ε

Jako další příklad lze uvést gramatiku pro podmnožinu hraček anglický jazyk darováno:

terminály

{generovat, nenávidět, skvěle, zeleně, nápady, lingvisté}

neterminály

{VĚTA, NOUNPHRASE, VERBPHRASE, NOUN, VERB, ADJ}

výrobní pravidla

VĚTA → JMENNÁ FRÁZE SLOVESNÁ FRÁZE

JMENNÁ FRÁZE → ADJ JMENNÁ FRÁZE

JMENNÁ FRÁZE → PODSTATNÉ JMÉNO

SLOVESNÁ FRÁZE → SLOVESO JMENNÁ FRÁZE

SLOVESNÁ FRÁZE → SLOVESO

PODSTATNÉ JMÉNO → nápady

PODSTATNÉ JMÉNO → lingvisté

SLOVESO → generovat

SLOVESO → nenávist

ADJ → skvělý

ADJ → zelená

a začátek symbolu VĚTA. Příkladem odvození je

VĚTA → HLASOVÁ VERBPHRÁZA → PŘIZPŮSOBTE HLASOVOU VERBPÁZU → ADJ NOUN VERBPHRASE → PŘIZPŮSOBTE HLASOVOU HLASOVOU HLASU → ADJ NOUN VERB ADJ NOUNPHRASE → ADJ NOUN VERB ADJ ADJ NOUNPHRASE → ADJ NOUN SLOVO ADJ ADJ NOUN → skvělé NOUN VERB ADJ ADJ NOUN → skvělí lingvisté VERB ADJ ADJ NOUN → skvělí lingvisté generují ADJ ADJ NOUN → skvělí lingvisté generují skvěle ADJ NOUN → skvělí lingvisté vytvářejí skvělou zelenou PODSTATNÉ JMÉNO → skvělí lingvisté vytvářejí skvělé zelené nápady.

Další posloupnosti, které lze odvodit z této gramatiky, jsou: "nápady nenávidí skvělé lingvisty", a "nápady se generují". I když jsou tyto věty nesmyslné, jsou syntakticky správné. Syntakticky nesprávná věta (např."nápady nápady velká nenávist") nelze z této gramatiky odvodit. Viz"Bezbarvé zelené nápady zuřivě spí „pro podobný příklad, který uvedl Chomsky v roce 1957; viz Gramatická struktura fráze a Pravidla struktury frází více přirozený jazyk příklady a problémy formální gramatika v této oblasti.

Hierarchie

Nastavit inkluze popsané Chomského hierarchií

Následující tabulka shrnuje každý z Chomského čtyř typů gramatik, třídu jazyka, kterou generuje, typ automatu, který jej rozpozná, a formu, kterou musí mít jeho pravidla.

Gramatika	Jazyky	Automat	Pravidla produkce (omezení) *	Příklady[3]
Typ-0	Rekurzivně vyčíslitelné	Turingův stroj	${displaystyle gamma ightarrow alfa}$ (bez omezení)	${displaystyle L = {w | w}$ popisuje koncový Turingův stroj${displaystyle}}$
Typ 1	Kontextové	Lineárně ohraničený nedeterministický Turingův stroj	${displaystyle alfa A eta ightarrow alfa gama eta}$	${displaystyle L = {a ^ {n} b ^ {n} c ^ {n} | n> 0}}$
Typ-2	Bez kontextu	Nedeterministické zasunovací automat	${displaystyle Aightarrow alfa}$	${displaystyle L = {a ^ {n} b ^ {n} | n> 0}}$
Typ 3	Pravidelný	Konečný stavový automat	${displaystyle Aightarrow {ext {a}}}$ a ${displaystyle Aightarrow {ext {a}} B}$	${displaystyle L = {a ^ {n} | ngeq 0}}$
* Význam symbolů: ${displaystyle {ext {a}}}$ = terminál ${displaystyle A}$, ${displaystyle B}$ = nekoncové ${displaystyle alpha}$, ${displaystyle eta}$, ${displaystyle gamma}$ = řetězec terminálů a / nebo terminálů ${displaystyle alpha}$, ${displaystyle eta}$ = možná prázdný ${displaystyle gamma}$ = nikdy prázdný

Všimněte si, že sada gramatik odpovídá rekurzivní jazyky není členem této hierarchie; to by bylo správně mezi Type-0 a Type-1.

Každý běžný jazyk je bezkontextový, každý bezkontextový jazyk je citlivý na kontext, každý kontextově citlivý jazyk je rekurzivní a každý rekurzivní jazyk je rekurzivně spočetný. Jedná se o všechny správné inkluze, což znamená, že existují rekurzivně vyčíslitelné jazyky, které nejsou kontextově závislé, kontextově citlivé jazyky, které nejsou kontextové a bezkontextové jazyky, které nejsou běžné.^[4]

Gramatiky typu 0

Gramatiky typu 0 zahrnují všechny formální gramatiky. Generují přesně všechny jazyky, které dokáže a Turingův stroj. Tyto jazyky jsou také známé jako rekurzivně spočetné nebo Turing rozpoznatelný jazyky.^[5] Všimněte si, že se to liší od rekurzivní jazyky, který může být rozhodl podle vždy se zastavující Turingův stroj.

Gramatiky typu 1

Generování gramatik typu 1 kontextově citlivé jazyky. Tyto gramatiky mají pravidla formy ${displaystyle alfa A eta ightarrow alfa gama eta}$ s ${displaystyle A}$ neterminál a ${displaystyle alpha}$, ${displaystyle eta}$ a ${displaystyle gamma}$ řetězce terminálů a / nebo neterminálů. Řetězce ${displaystyle alpha}$ a ${displaystyle eta}$ může být prázdný, ale ${displaystyle gamma}$ musí být neprázdné. Pravidlo ${displaystyle Sightarrow epsilon}$ je povoleno, pokud ${displaystyle S}$ nezobrazí se na pravé straně žádného pravidla. Jazyky popsané v těchto gramatikách jsou přesně všechny jazyky, které lze rozpoznat pomocí a lineárně ohraničený automat (nedeterministický Turingův stroj, jehož páska je ohraničena konstantním časem délky vstupu.)

Gramatiky typu 2

Gramatiky typu 2 generují bezkontextové jazyky. Ty jsou definovány pravidly formuláře ${displaystyle Aightarrow alfa}$ s ${displaystyle A}$ být neterminálem a ${displaystyle alpha}$ být řetězec terminálů a / nebo neterminálů. Tyto jazyky jsou přesně všechny jazyky, které lze rozpoznat nedeterministicky zasunovací automat. Bezkontextové jazyky - nebo spíše jejich podmnožina deterministický bezkontextový jazyk —Je teoretický základ pro strukturu frází většiny programovací jazyky, i když jejich syntaxe zahrnuje také kontextové rozlišení jmen z důvodu prohlášení a rozsah. K usnadnění analýzy se často používá podmnožina gramatik, například pomocí Analyzátor LL.

Gramatiky typu 3

Gramatiky typu 3 generují běžné jazyky. Taková gramatika omezuje svá pravidla na jediný neterminál na levé straně a pravou stranu skládající se z jediného terminálu, případně následovaného jediným neterminálem (pravý regulární). Alternativně může pravá strana gramatiky sestávat z jednoho terminálu, kterému může předcházet jeden neterminál (levý regulární). Ty generují stejné jazyky. Pokud jsou však kombinována pravidla levého a regulárního pravidla, jazyk již nemusí být pravidelný. Pravidlo ${displaystyle Sightarrow epsilon}$ je zde také povoleno, pokud ${displaystyle S}$ nezobrazí se na pravé straně žádného pravidla. Tyto jazyky jsou přesně všechny jazyky, o kterých může rozhodnout a konečný stavový automat. Tuto rodinu formálních jazyků lze navíc získat prostřednictvím regulární výrazy. Běžné jazyky se běžně používají k definování vzorů vyhledávání a lexikální struktury programovacích jazyků.

Reference

• Chomsky, Noame (1959). „O určitých formálních vlastnostech gramatik“ (PDF). Informace a kontrola. 2 (2): 137–167. doi:10.1016 / S0019-9958 (59) 90362-6.
• Chomsky, Noame; Schützenberger, Marcel P. (1963). "Algebraická teorie bezkontextových jazyků". In Braffort, P .; Hirschberg, D. (eds.). Počítačové programování a formální jazyky (PDF). Amsterdam: Severní Holandsko. str. 118–161.
• Davis, Martin D .; Sigal, Ron; Weyuker, Elaine J. (1994). Vyčíslitelnost, složitost a jazyky: Základy teoretické informatiky (2. vyd.). Boston: Academic Press, Harcourt, Brace. p.327. ISBN  0-12-206382-1.