Detail publikace

Phrase-Structure Grammars: Normal Forms and Reduction

KŘIVKA Zbyněk, MEDUNA Alexander a ZEMEK Petr. Phrase-Structure Grammars: Normal Forms and Reduction. The Computer Journal, roč. 59, č. 8, 2016, s. 1180-1185. ISSN 0010-4620.
Název česky
Obecné gramatiky: Normální formy a redukce
Typ
článek v časopise
Jazyk
angličtina
Autoři
Křivka Zbyněk, Ing., Ph.D. (UIFS FIT VUT)
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
Zemek Petr, Ing. (UIFS FIT VUT)
Abstrakt

Článek zavádí dvě nové normální formy pro obecné gramatiky, ve kterých mají bezkontextová i nebezkontextová pravidla předepsanou formu. Navíc je omezen počet bezkontextových pravidel. Přesněji řečeno, první forma má 2 + n bezkontextových pravidel, kde n je počet terminálů. V případě nebezkontextových pravidel je každé tvaru AB -> CD, kde A, B, C, D jsou neterminály. Druhá normální forma má vždy dvě bezkontextová pravidla, S -> S# a # -> e, kde S je počáteční symbol, # je neterminál a e je prázdný řetězec. V případě, že uvažujeme nebezkontextová pravidla, každé j tvaru AB -> XD, kde A, B, D jsou neterminály a X je neterminál nebo terminál.

Rok
2016
Strany
1180-1185
Časopis
The Computer Journal, roč. 59, č. 8, ISSN 0010-4620
Vydavatel
Oxford University Press
DOI
10.1093/comjnl/bxw001
UT WoS
000384669900006
EID Scopus
2-s2.0-84992146174
BibTeX 
@ARTICLE{FITPUB9949,
   author = "Zbyn\v{e}k K\v{r}ivka and Alexander Meduna and Petr Zemek",
   title = "Phrase-Structure Grammars: Normal Forms and Reduction",
   pages = "1180--1185",
   journal = "The Computer Journal",
   volume = 59,
   number = 8,
   year = 2016,
   ISSN = "0010-4620",
   doi = "10.1093/comjnl/bxw001",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9949"
}
Nahoru