NORMÁLNÍ FORMA CHOMSKÉHO
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é.
- Č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.
URL: https://www.czechency.org/slovnik/NORMÁLNÍ FORMA CHOMSKÉHO (poslední přístup: 19. 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