2018/05/10 by Reghizzi, Stefano Crespi, Pietro, Pierluigi San
#F.1.1 #F.1.4 #FL #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.1805.04003
The famous theorem by Chomsky and Schützenberger (CST) says that every context-free language L over an alphabet Σ is representable as h(D ∩ R), where D is a Dyck language over a set Ω of brackets, R is a local language and h is an alphabetic homomorphism that erases unboundedly many symbols. Berstel found that the number of erasures can be linearly limited if the grammar is in Greibach normal form; Berstel and Boasson (and later, independently, Okhotin) proved a non-erasing variant of CST for grammars in Double Greibach Normal Form. In all these CST statements, however, the size of the Dyck alphabet Ω depends on the grammar size for L. In the Stanley variant of the CST, |Ω| only depends on |Σ| and not on the grammar, but the homomorphism erases many more symbols than in the other versions of CST; also, the regular language R is strictly locally testable but not local. We prove a new version of CST which combines both features of being non-erasing and of using a grammar-independent alphabet. In our construction, |Ω| is polynomial in |Σ|, namely O(|Σ|46), and the regular language R is strictly locally testable. Using a recent generalization of Medvedev's homomorphic characterization of regular languages, we prove that the degree in the polynomial dependence of |Ω| on |Σ| may be reduced to just 2 in the case of linear grammars in Double Greibach Normal Form.