Publication Details

On Normal Forms and Erasing Rules in Path-Controlled Grammars

KOUTNÝ Jiří and MEDUNA Alexander. On Normal Forms and Erasing Rules in Path-Controlled Grammars. Schedae Informaticae, vol. 2013, no. 22, 2014, pp. 9-18. ISSN 0860-0295. Available from: http://www.ejournals.eu/Schedae-Informaticae/Volume-22/art/2848/
Czech title
O normálních formách a vymazávacích pravidlech gramatik řízených cestou
Type
journal article
Language
english
Authors
Koutný Jiří, Ing. (DIFS FIT BUT)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
URL
Keywords

context-free grammars, path controlled grammars, restricted derivation trees, paths, normal forms, erasing rules

Abstract

This paper discusses path controlled grammars-context-free grammars with a root-to-leaf path in their derivation trees restricted by a control language. First, it investigates the impact of erasing rules on the generative power of path controlled grammars. Then, it establishes two Chomsky-like
normal forms for path controlled grammars-the first allows unit rules, the second allows just one erasing rule.

Published
2014
Pages
9-18
Journal
Schedae Informaticae, vol. 2013, no. 22, ISSN 0860-0295
DOI
10.4467/20838476SI.13.001.2086
EID Scopus
2-s2.0-85020891879
BibTeX 
@ARTICLE{FITPUB9896,
   author = "Ji\v{r}\'{i} Koutn\'{y} and Alexander Meduna",
   title = "On Normal Forms and Erasing Rules in Path-Controlled Grammars",
   pages = "9--18",
   journal = "Schedae Informaticae",
   volume = 2013,
   number = 22,
   year = 2014,
   ISSN = "0860-0295",
   doi = "10.4467/20838476SI.13.001.2086",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9896"
}
Back to top