TY - JOUR

T1 - The hardest language for grammars with context operators

AU - Мрыхин, Михаил Кириллович

AU - Охотин, Александр Сергеевич

PY - 2023/5/22

Y1 - 2023/5/22

N2 - 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.

AB - 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.

KW - Finite transducers

KW - Formal grammars

KW - Formal language theory

KW - Grammars with context operators

KW - Hardest formal languages

KW - Inverse homomorphisms

UR - https://www.mendeley.com/catalogue/34005955-b164-35cc-bbab-7502766ac2b5/

U2 - 10.1016/j.tcs.2023.113829

DO - 10.1016/j.tcs.2023.113829

M3 - статья

VL - 958

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

M1 - 113829

ER -