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
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
UT WoS
000384669900006
EID Scopus
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