KONTEXTOVÁ GRAMATIKA

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

Vymezení a popis přirozených jazyků (zejména jejich syntaktické struktury); typ ↗generativní gramatiky↗Chomského hierarchii gramatik a jazyků; nazývá se také gramatikou typu 1. Přepisovací pravidla k.g. 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; k.g. je tedy typem gramatiky nezkracující, tj. délka větných forem vzniklých v průběhu derivace neklesá. Alternativní definicí je toto omezení kladené na pravidla: α → β, kde α a β jsou řetězce, kde α obsahuje aspoň jeden neterminál a řetězec β není kratší než řetězec α. Protějškem k.g. mezi automaty je tzv. lineárně omezený automat jakožto speciální případ Turingova stroje. K.g. generují třídu ↗kontextových jazyků (což je podtřída rekurzivních množin), dokážou tedy generovat i všechny ↗bezkontextové jazyky a navíc dokážou modelovat i nebezkontextové, tj. nezapouštějící struktury typu a1, a2, an, b1, b2, bn (n ≥ 0), kde prvky ai a bi jsou spolu v syntaktickém vztahu, a struktury s nespojitými/nesouvislými složkami, v nichž se mezi členy složky nachází – z hlediska slovosledu – element, který do ní nepatří. Tyto schopnosti k.g. jsou dány tím, že na rozdíl od ↗bezkontextových gramatik dokážou k.g. přehazovat symboly v průběhu derivace. K.g. představují horní mez strukturní složitosti přirozených jazyků; struktura všech přirozených jazyků světa se dá postihnout jistou podtřídou k.g. Reálně se při modelování přirozených jazyků pracuje s gramatikami, které jsou konzervativním rozšířením bezkontextových gramatik (např. gramatiky typu tree‑adjoining, v nichž se operuje nikoli s řetězci, nýbrž se stromovými strukturami).

Literatura
  • Češka, M. Gramatiky a jazyky, 1992.
  • 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.
  • 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.
  • Rozenberg, G. & A. Salomaa. (eds.) Handbook of Formal Languages 1–3, 1997.
  • Salomaa, A. Formal Languages, 1973.
  • Savitch, W. J. & E. Bach ad. (eds.) The Formal Complexity of Natural Language, 1987, 320–334.
Citace
Vladimír Petkevič (2017): KONTEXTOVÁ GRAMATIKA. In: Petr Karlík, Marek Nekula, Jana Pleskalová (eds.), CzechEncy - Nový encyklopedický slovník češtiny.
URL: https://www.czechency.org/slovnik/KONTEXTOVÁ GRAMATIKA (poslední přístup: 24. 4. 2024)

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

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

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