Comparing consecutive letter counts in multiple context-free languages

Florian Lehner; Christian Lindorfer

paper

Comparing consecutive letter counts in multiple context-free languages

arXiv:2002.08236

Abstract

Context-free grammars are not able to model cross-serial dependencies in natural languages. To overcome this issue, Seki et al. introduced a generalization called $m$ -multiple context-free grammars ( $m$ -MCFGs), which deal with $m$ -tuples of strings. We show that $m$ -MCFGs are capable of comparing the number of consecutive occurrences of at most $2 m$ different letters. In particular, the language ${a_{1}^{n_{1}} a_{2}^{n_{2}} \dots a_{k}^{n_{2 m + 1}} ∣ n_{1} \geq n_{2} \geq \dots \geq n_{2 m + 1} \geq 0}$ is $(m + 1)$ -multiple context-free, but not $m$ -multiple context-free.