Detail publikace

Phrase-Structure Grammars: Normal Forms and Reduction

KŘIVKA, Z.; MEDUNA, A.; ZEMEK, P. Phrase-Structure Grammars: Normal Forms and Reduction. COMPUTER JOURNAL, 2016, vol. 59, no. 8, p. 1180-1185. ISSN: 0010-4620.
Název česky
Obecné gramatiky: Normální formy a redukce
Typ
článek v časopise
Jazyk
anglicky
Autoři
Křivka Zbyněk, Ing., Ph.D. (UIFS)
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Zemek Petr, Ing., Ph.D.
Klíčová slova

formal languages, phrase-structure grammars, normal forms

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
COMPUTER JOURNAL, roč. 59, č. 8, ISSN 0010-4620
DOI
10.1093/comjnl/bxw001
UT WoS
000384669900006
EID Scopus
2-s2.0-84992146174
BibTeX 
@article{BUT130900,
  author="Zbyněk {Křivka} and Alexandr {Meduna} and Petr {Zemek}",
  title="Phrase-Structure Grammars: Normal Forms and Reduction",
  journal="COMPUTER JOURNAL",
  year="2016",
  volume="59",
  number="8",
  pages="1180--1185",
  doi="10.1093/comjnl/bxw001",
  issn="0010-4620",
  url="https://www.fit.vut.cz/research/publication/9949/"
}
Nahoru