A note on undercover relation (Q2265818): Difference between revisions

The paper gives a new characterization of the undercover relation between context-free grammars [see \textit{E. Soisalon-Soininen} and \textit{D. Wood}, Acta Inf. 17, 435-449 (1982; Zbl 0478.68086) for definition and motivation] in the semi-Greibach normal form (with right hand members of rules of the form \(b\alpha\), where b is a terminal symbol or it is empty and \(\alpha\) is a string of nonterminals). Based on this characterization (which involves homomorphism equivalence problem) it is proved that it is decidable whether a context-free grammar \(G_ 1\) undercovers a context- free grammar \(G_ 2\) with respect to a homomorphism (both \(G_ 1\), \(G_ 2\) are in semi-Greibach normal form).