2020/12/07 by Mrykhin, Mikhail, Okhotin, Alexander
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2012.03596
In 1973, Greibach ("The hardest context-free language", SIAM J. Comp., 1973) constructed a context-free language L0 with the property that every context-free language can be reduced to L0 by a homomorphism, thus representing it as an inverse homomorphic image h-1(L0). In this paper, a similar characterization is established for a family of grammars equipped with operators for referring to the left context of any substring, recently defined by Barash and Okhotin ("An extension of context-free grammars with one-sided context specifications", Inform. Comput., 2014). An essential step of the argument is a new normal form for grammars with context operators, in which every nonterminal symbol defines only strings of odd length in left contexts of even length: the even-odd normal form. The characterization is completed by showing that the language family defined by grammars with context operators is closed under inverse homomorphisms; actually, it is closed under injective nondeterministic finite transductions.