Detail publikace
On the Generation of Sentences with Their Parses by Propagating Regular-Controlled Grammars
Originální název
On the Generation of Sentences with Their Parses by Propagating Regular-Controlled Grammars
Anglický název
On the Generation of Sentences with Their Parses by Propagating Regular-Controlled Grammars
Jazyk
en
Originální abstrakt
The present paper explains how to transform any regular-controlled (context-free) grammar with appearance checking G to a propagating regular-controlled (context-free) grammar with appearance checking G' whose language L(G') has sentences of the form wz, where w is in L(G) and z is a parse of w in G'. Consequently, for every recursively enumerable language K, there exists a propagating regular-controlled grammar with appearance checking G' with L(G') of the above form so that K results from L(G') by erasing all rules in L(G'). In addition, analogical results are established (a) in terms of these grammars without appearance checking and (b) in terms of these grammars that make only leftmost derivations. In the conclusion, we point out some consequences implied by the results achieved in this paper.
Anglický abstrakt
The present paper explains how to transform any regular-controlled (context-free) grammar with appearance checking G to a propagating regular-controlled (context-free) grammar with appearance checking G' whose language L(G') has sentences of the form wz, where w is in L(G) and z is a parse of w in G'. Consequently, for every recursively enumerable language K, there exists a propagating regular-controlled grammar with appearance checking G' with L(G') of the above form so that K results from L(G') by erasing all rules in L(G'). In addition, analogical results are established (a) in terms of these grammars without appearance checking and (b) in terms of these grammars that make only leftmost derivations. In the conclusion, we point out some consequences implied by the results achieved in this paper.
BibTex
@article{BUT103400,
author="Alexandr {Meduna} and Petr {Zemek}",
title="On the Generation of Sentences with Their Parses by Propagating Regular-Controlled Grammars",
annote="The present paper explains how to transform any regular-controlled (context-free)
grammar with appearance checking G to a propagating regular-controlled
(context-free) grammar with appearance checking G' whose language L(G') has
sentences of the form wz, where w is in L(G) and z is a parse of w in G'.
Consequently, for every recursively enumerable language K, there exists
a propagating regular-controlled grammar with appearance checking G' with L(G')
of the above form so that K results from L(G') by erasing all rules in L(G'). In
addition, analogical results are established (a) in terms of these grammars
without appearance checking and (b) in terms of these grammars that make only
leftmost derivations. In the conclusion, we point out some consequences implied
by the results achieved in this paper.",
address="NEUVEDEN",
chapter="103400",
doi="10.1016/j.tcs.2012.12.040",
edition="NEUVEDEN",
howpublished="print",
institution="NEUVEDEN",
number="1",
volume="477",
year="2013",
month="february",
pages="67--75",
publisher="NEUVEDEN",
type="journal article - other"
}