Publication Details
On Normal Forms and Erasing Rules in Path-Controlled Grammars
KOUTNÝ, J.; MEDUNA, A. On Normal Forms and Erasing Rules in Path-Controlled Grammars. Schedae Informaticae, 2014, vol. 2013, no. 22, p. 9-18. ISSN: 0860-0295.
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., Ph.D.
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
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
EID Scopus
BibTeX
@article{BUT111480,
author="Jiří {Koutný} and Alexandr {Meduna}",
title="On Normal Forms and Erasing Rules in Path-Controlled Grammars",
journal="Schedae Informaticae",
year="2014",
volume="2013",
number="22",
pages="9--18",
doi="10.4467/20838476SI.13.001.2086",
issn="0860-0295",
url="http://www.ejournals.eu/Schedae-Informaticae/Volume-22/art/2848/"
}