Chomsky hierarchie
Chomsky hierarchie je hierarchie omezení tříd formálních gramatik to tvořit formální jazyky. Tato hierarchie byla popisována Noam Chomsky v 1956.
| Tabulka s obsahem |
| 1 formální gramatiky 2 hierarchie 3 odkazy |
Formální gramatika sestává z konečného souboru symbolů terminálu (dopisy slov ve formálním jazyce), konečný soubor nonterminal symbolů, soubor pravidel výroby s odešel - a pravá strana sestávat ze slova o těchto symbolech a symbolu začátku. Pravidlo může být aplikováno na slovo narazením left-hand bok po pravorukou boku. Původ je sled aplikací pravidla. Takový gramatika definuje formální jazyk všech slov se sestávat pouze terminálu symboly, které mohou být sáhly původem od začátku symbol.
Nonterminals je obvykle reprezentován velkými dopisy, terminály malými písmeny a symbolem začátku “S”. Například, gramatika s terminály {, b}, nonterminals {S,, B}, výroba rozhodne
- S - > absolutní
- S - > a epsilon; (s a epsilon; prázdný řetězec)
- BA - > AB
- BS - > b
- Bb - > bb
- Ab - > ab
- Aa - > aa
Viďte formální gramatiku pro více komplikované vysvětlení.
Chomsky hierarchie sestává z následujících úrovní:
- Psát-0 gramatiky (neomezené gramatiky) zahrnují všechny formální gramatiky. Oni vytvářejí přesně všechny jazyky, které mohou být rozpoznány Turing strojem. Jazyk, který je rozpoznán Turing strojem je definován jako všechny řetězce na kterém to se zastaví. Tyto jazyky jsou také známé jako rekurzívně enumerable jazyky. Poznamenat, že toto je odlišné od rekurzivních jazyků který může být rozhodnutý vždy váhavým Turing strojem.
- Psát-1 gramatiky (kontextové gramatiky) tvoří kontextové jazyky. Tyto gramatiky mají pravidla formy a alpha;a beta; - > a alpha; a gama; a beta; s nonterminal a a alpha;, a beta; a a gama; řetězy terminálů a nonterminals. Řetězce a alpha; a a beta; smět být prázdný, ale a gama; muset být nonempty. Pravidlo S - > a epsilon; je dovolen jestliže S se neobjeví na pravé straně nějakého pravidla. Jazyky popsané těmito gramatikami jsou přesně všechny jazyky, které mohou být rozpoznány non-deterministický Turing stroj jehož páska je ohraničena konstantou měří délku vstupu.
- Psát-2 gramatiky (kontext-uvolnit gramatiky) tvořit kontext-uvolnit jazyky. Tito jsou definováni pravidly formy - > a gama; s nonterminal a a gama; řetěz terminálů a nonterminals. Tyto jazyky jsou přesně všechny jazyky, které mohou být rozpoznány non-deterministický automat pushdown. Kontext volné jazyky jsou teoretické východisko pro syntax nejvíce programovací jazyky.
- Psát-3 gramatiky (pravidelné gramatiky) tvoří pravidelné jazyky. Takový gramatika omezí jeho vlády k jedinému nonterminal na left-hand strana a pravá strana sestávat z jediného terminálu, možná následovaný jediným nonterminal. Pravidlo S - > a epsilon; je také tady povolený jestliže S se neobjeví na pravé straně nějakého pravidla. Tyto jazyky jsou přesně všechny jazyky, které mohou být rozhodnuty konečným státním automatem. Dále, tato rodina formálních jazyků může být získána pravidelnými výrazy. Pravidelné jazyky jsou běžně používané definovat vzory hledání a lexikální strukturu programovacích jazyků.
Následující stůl shrne každého Chomsky je čtyři druhy gramatik, třída jazyků to vytváří, druh automatu, který rozpozná to a formy jeho pravidla musí mít.
| Gramatika | Jazyky | Automat | Pravidla výroby |
|---|---|---|---|
| Psát-0 | Rekurzívně enumerable | Turing stroj | Žádná omezení |
| Psát-1 | Kontextový | Lineární-ohraničené non-deterministický Turing stroj | a alpha;a beta; - > a alpha; a gama; a beta; |
| Psát-2 | Kontext-volný | Non-deterministický pushdown automat | - > a gama; |
| Psát-3 | Pravidelný | Konečný státní automat | - > aB - > |
- Noam Chomsky: Tři modely pro popis jazyka, transakce zloby na informační teorii, 2 (1956), 113 stran-124
- Noam Chomsky: Na jistých formálních vlastnostech gramatik, informace a kontrola, 1 (1959), 91 stran-112