Zu diesem lizenzpflichtigen Artikel gibt es eine Open Access Version, die kostenlos und ohne Lizenzbeschränkung gelesen werden kann. Die Open Access Version kann inhaltlich von der lizenzpflichtigen Version abweichen.
Preisinformation
Bitte wählen Sie ihr Lieferland und ihre Kundengruppe
A context-free grammar G with terminal vocabulary sigma is left universal for a class of languages L with respect to a class of languages L1 if for each language let L be a subset of sigmastar in L, a control language C in L1 can be found such that G controlled by C generates L by leftmost derivations. We show that for a class of languages L and a class of languages L1, if L1 is closed under homomorphism and inverse homomorphism, then for each alphabet sigma, the following two statements are equivalent. 1) There exists a context-free grammar with terminal vocabulary sigma which is left universal for L with respect to L1. 2) There exist a context-free language L1 and a homomorphism h such that each language let L be a subset of sigmastar in L equals h(L1 is the sum-set from L(exp')) for some L(exp') in L1. We also give some applications of this result.