REGULÁRNÍ GRAMATIKA

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

Nejslabší typ ↗generativní gramatiky v Chomského hierarchii gramatik (viz ↗Chomského hierarchie gramatik a jazyků). Nazývá se také gramatika konečněstavová nebo gramatika typu 3. Přepisovací pravidla r.g. mají dvojí podobu: X → a, n. X → aB, kde X, B jsou neterminální symboly, a je terminální symbol. Taková gramatika se nazývá pravá lineární r.g. Pokud mají všechna pravidla podobu X → a, n. X → Ba, nazývá se taková gramatika levá lineární r.g. Oba podtypy r.g. generují ↗regulární jazyky (konečněstavové jazyky), přičemž každý regulární jazyk lze generovat pravou i levou lineární r.g. Mezi automaty odpovídá r.g. pojem konečněstavového automatu, neboť r.g. mají jen „konečnou paměť“, kterou lze vyjádřit konečným počtem stavů automatu. R.g. spolu s odpovídajícími automaty mají ve ↗formální lingvistice, v ↗matematické lingvistice a v ↗počítačové lingvistice nesmírně široké uplatnění: modelují se jimi všechny podvětné úseky jazyka (zejm. slovo a jeho struktura) a též jednodušší syntaktické struktury, jež lze modelovat regulárními výrazy (např. nominální frázi); r.g. však nedokážou generovat struktury s neomezeným ↗sebezapouštěním (angl. self‑embedding) jako ↗bezkontextové gramatiky a ↗kontextové gramatiky. Užívá se jich tedy pro ↗parsing jednodušších struktur, ↗morfologickou disambiguaci, zpracování morfologie (např. v tzv. dvouúrovňové morfologii) a mnoho dalších druhů zpracování jazyka. Matematicky je jejich velkou výhodou, že třída regulárních (konečněstavových) jazyků je na rozdíl od třídy ↗bezkontextových jazyků a ↗kontextových jazyků uzavřena na všechny hlavní množinové a algebraické operace (sjednocení, průnik, doplněk, rozdíl, sřetězení, Kleenův uzávěr, levý a pravý kvocient a další), takže úlohu řešitelnou r.g. (či konečným automatem) lze rozložit na úkoly dílčí, jež jsou řešitelné dílčími r.g., a pak dílčí moduly spojit ve výslednou komplexní r.g. R.g. navíc přesně vystihují pojem regulárního výrazu hojně používaného v ↗počítačové lingvistice včetně ↗lingvistiky korpusové.

Literatura
  • Habiballa, H. Regulární a bezkontextové jazyky, 2005.
  • 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.
  • Partee, B. H. & A. ter Meulen ad. Mathematical Methods in Linguistics, 1990.
  • Roche, E. & Y. Schabes. (eds.) Finite-State Language Processing, 1997.
  • 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): REGULÁRNÍ GRAMATIKA. In: Petr Karlík, Marek Nekula, Jana Pleskalová (eds.), CzechEncy - Nový encyklopedický slovník češtiny.
URL: https://www.czechency.org/slovnik/REGULÁRNÍ GRAMATIKA (poslední přístup: 25. 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