cs.FL
The hardest language for grammars with context operators. In 1973, Greibach ("The hardest context free language", SIAM J. Comp., 1973) constructed a context free language L 0 with the property that every context free language can be reduced to L 0 by a homomorphism, thus representing it as an inverse homomorphic image h 1 (L 0) . 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.