A categorial grammar assigns one of several synthetic categories to each symbol of the alphabet, and the category of a string is then deduced from the categories assigned to its symbols using two simple reduction rules. A subclass of categorial grammars, in which only one category is assigned to each symbol, thus eliminating ambiguity on the lexical level, has been studied under multiple names, such as rigid, 1-valued or deterministic categorial grammars. While unrestricted categorial grammars are equivalent to the context-free grammars, the proposed subclass initially appears weak, as it cannot define even some regular languages. This paper investigates the expressive power of this subclass; it is proved that it is actually powerful enough to define a homomorphic encoding of every context-free language, in the sense that for every context-free language L over an alphabet <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\Sigma $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Σ</mi> </math></EquationSource> </InlineEquation> there is a language <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$L'$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>L</mi> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation> over some alphabet <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\Omega $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Ω</mi> </math></EquationSource> </InlineEquation> defined by categorial grammar with unique category assignment and a homomorphism <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$h :\Sigma \rightarrow \Omega ^+$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>h</mi> <mo>:</mo> <mi mathvariant="normal">Σ</mi> <mo stretchy="false">→</mo> <msup> <mi mathvariant="normal">Ω</mi> <mo>+</mo> </msup> </mrow> </math></EquationSource> </InlineEquation>, such that a string w is in L if and only if h(w) is in <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$L'$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>L</mi> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation>. In particular, in Greibach’s hardest context-free language theorem, it is sufficient to use a hardest language defined by a categorial grammar with unique category assignment.

On the expressive power of categorial grammars with unique category assignment

期刊论文
发表日期：

2025年11月1日

查看全文

Maxim Vishnikin,
Alexander Okhotin

摘要

A categorial grammar assigns one of several synthetic categories to each symbol of the alphabet, and the category of a string is then deduced from the categories assigned to its symbols using two simple reduction rules. A subclass of categorial grammars, in which only one category is assigned to each symbol, thus eliminating ambiguity on the lexical level, has been studied under multiple names, such as rigid, 1-valued or deterministic categorial grammars. While unrestricted categorial grammars are equivalent to the context-free grammars, the proposed subclass initially appears weak, as it cannot define even some regular languages. This paper investigates the expressive power of this subclass; it is proved that it is actually powerful enough to define a homomorphic encoding of every context-free language, in the sense that for every context-free language L over an alphabet $\Sigma $ $Σ$ there is a language $L'$ $L^{'}$ over some alphabet $\Omega $ $Ω$ defined by categorial grammar with unique category assignment and a homomorphism $h :\Sigma \rightarrow \Omega ^+$ $h : Σ \to Ω^{+}$ , such that a string w is in L if and only if h(w) is in $L'$ $L^{'}$ . In particular, in Greibach’s hardest context-free language theorem, it is sufficient to use a hardest language defined by a categorial grammar with unique category assignment.