NORMÁLNÍ FORMA CHOMSKÉHO

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

Jedna ze standardizací podoby pravidel ↗bezkontextové gramatiky. Jestliže obecná bezkontextová gramatika obsahuje přepisovací pravidla typu X → α, kde X je neterminální symbol a α je řetězec složený z terminálů a/nebo neterminálů, pak bezkontextová gramatika v n.f.Ch. obsahuje jen pravidla těchto dvou typů: (i) X → a, kde X je neterminální symbol, a je symbol terminální, nebo (ii) X → BC, kde X, B, C jsou neterminální symboly (viz také ↗terminál a neterminál v syntaktické struktuře). Platí, že každý ↗bezkontextový jazyk s výjimkou takového, který obsahuje prázdný řetězec, se dá vygenerovat nějakou gramatikou v n.f.Ch. (prázdný řetězec se však v případě potřeby dá vygenerovat jediným zvláštním pravidlem S → λ, kde S je počáteční symbol gramatiky a λ prázdný řetězec). Bezkontextová gramatika v n.f.Ch. generuje nejvýše binární ↗bezprostředněsložkové stromy (frázové stromy). N.f.Ch. je východiskem pro ↗normální formu Greibachové.

Literatura
  • Češka, M. Gramatiky a jazyky, 1992.
  • 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.
  • 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.
  • Oehrle, R. T. & E. Bach ad. (eds.) Categorial Grammars and Natural Language Structures, 1988.
  • 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): NORMÁLNÍ FORMA CHOMSKÉHO. In: Petr Karlík, Marek Nekula, Jana Pleskalová (eds.), CzechEncy - Nový encyklopedický slovník češtiny.
URL: https://www.czechency.org/slovnik/NORMÁLNÍ FORMA CHOMSKÉHO (poslední stažení: 19. 11. 2017)

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

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

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