论文标题
语法和上下文运营商的最难语言
The hardest language for grammars with context operators
论文作者
论文摘要
1973年，Greibach（“最困难的无上下文语言”，Siam J. Comp。，1973）与该属性一起构建了一种无上下文的语言$ L_0 $，同型可以将每个无上下文的语言降低到$ L_0 $，从而将其表示为反向同源图像$ H^{-1}（-1}（L_0）$。在本文中，为配备了操作员的语法家族建立了类似的特征，以指代任何由Barash and Okhotin定义的任何子字符串的左下文（“具有单方面上下文规格的无上下文语法扩展”，Inform。Comput。，2014年）。该论点的一个必要步骤是具有上下文操作员语法的新正常形式，其中每个非终端符号仅在均匀长度的左上文中定义了奇数长的字符串：均匀的odd正常形式。表征是通过表明语法定义的具有上下文运算符的语言家族在逆同态下封闭的。实际上，它在不确定性的有限转置下被关闭。
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.
