CHOMSKÉHO HIERARCHIE GRAMATIK A JAZYKŮ

Základní
Rozšiřující

Vymezení a popis přirozených jazyků (zejména jejich syntaktické struktury). Podle omezení kladených na tvar přepisovacích pravidel v ↗generativních gramatikách se definuje Ch.h.g.j. generovaná těmito gramatikami. Je čtyřstupňová a jednotlivé stupně se označují čísly 0, 1, 2, 3:

(a) gramatiky a jazyky typu 0: na přepisovací pravidla gramatiky nejsou kladena žádná omezení (tj. jde tu o obecný přepisovací systém); tyto gramatiky generují největší třídu jazyků nazývaných rekurzivně spočetné jazyky a jejich slabá generativní síla (srov. ↗síla gramatiky) odpovídá tzv. obecnému Turingovu stroji;

(b) gramatiky a jazyky typu 1: na přepisovací pravidla gramatiky je kladeno omezení, že levá strana žádného pravidla nemá více symbolů než strana pravá, přičemž na levé straně každého pravidla se vyskytuje aspoň jeden neterminální symbol. Alternativní definice je tato: přepisovací pravidla mají tuto podobu: αXβ → αγβ, kde X je neterminální symbol, α a β jsou řetězce složené z terminálů a/nebo neterminálů, γ je neprázdný řetězec, na který se v kontextu (α, β) přepisuje symbol X. Takové gramatiky a jazyky se nazývají ↗kontextové gramatiky // nezkracující gramatiky a ↗kontextové jazyky // nezkracující jazyky;

(c) gramatiky a jazyky typu 2: levou stranu každého pravidla tvoří jediný neterminální symbol (schematicky X → α, kde α je řetězec složený z terminálů a/nebo neterminálů, může být i prázdný). Takové gramatiky a jazyky se nazývají ↗bezkontextové gramatiky // nekontextové gramatiky a ↗bezkontextové jazyky // nekontextové jazyky;

(d) gramatiky a jazyky typu 3: levou stranu každého pravidla tvoří vždy jediný neterminální symbol a pravou stranu tvoří buď jediný terminální symbol (schematicky X → a) n. jediný terminální symbol následovaný jediným neterminálním symbolem (X → aB). Takové gramatiky a jazyky se nazývají ↗regulární gramatiky // konečněstavové gramatiky a ↗regulární jazyky // konečněstavové jazyky.

Uvedené typy gramatik generují různé množiny jazyků, které jsou spolu vždy ve vztahu ostré inkluze – nejrozsáhlejší je množina jazyků typu 0, množina jazyků typu 1 je její vlastní podmnožinou atd. Vzhledem k tomu, že takováto základní škála gramatik a jazyků je velmi hrubá, byla definována celá řada dalších typů gramatik, které v Ch.h.g.j. tvoří jisté mezistupně (např. indexové gramatiky, tree‑adjoining gramatiky, tzv. head‑grammars aj.).

Literatura
  • Harrison, M. A. Introduction to Formal Language Theory, 1978.
  • Hausser, R. Foundations of Computational Linguistics. Human-Computer Communication in Natural Language, 2001.
  • Hopcroft, J. E. & J. D. Ullman. Formal Languages and their Relation to Automata, 1978.
  • Chomsky, N. Syntactic Structures, 1957 (č. překlad: Syntaktické struktury, 1966).
  • Chomsky, N. On Certain Formal Properties of Grammars. Information and Control 2, 1959, 137–167.
  • Chomsky, N. The Logical Structure of Linguistic Theory, 1975.
  • Chytil, M. Teorie automatů a formálních jazyků, 1978.
  • Chytil, M. Automaty a gramatiky, 1984.
  • Krulee, G. K. Computer Processing of Natural Language, 1991.
  • Levelt, W. J. M. An Introduction to the Theory of Formal Languages and Automata, 2008.
  • Manaster-Ramer, A. (ed.) Mathematics of Language, 1987.
  • Martinek, P. Základy teoretické informatiky, 2006.
  • Partee, B. H. & A. ter Meulen ad. Mathematical Methods in Linguistics, 1990.
  • Salomaa, A. Formal Languages, 1973.
  • Savitch, & E. Bach ad. (eds.) The Formal Complexity of Natural Language, 1987, 320–334.
  • Viz též Generativní gramatika.
  • Rozenberg, G. & A. Salomaa. (eds.) Handbook of Formal Languages 1–3, 1997.
Citace
Vladimír Petkevič (2017): CHOMSKÉHO HIERARCHIE GRAMATIK A JAZYKŮ. In: Petr Karlík, Marek Nekula, Jana Pleskalová (eds.), CzechEncy - Nový encyklopedický slovník češtiny.
URL: https://www.czechency.org/slovnik/CHOMSKÉHO HIERARCHIE GRAMATIK A JAZYKŮ (poslední přístup: 22. 8. 2019)

CzechEncy – Nový encyklopedický slovník češtiny

Všechna práva vyhrazena © Masarykova univerzita, Brno 2012–2018

Provozuje Centrum zpracování přirozeného jazyka