5
$\begingroup$

Unless I'm mistaken, a language of the form $\{0^a10^b\mid R(a,b)\}$ is context-free if and only if $R$ is a finite union of linear (in)equalities involving integer constants and the variables $a$ and $b$ with some modulo conditions, e.g., $R(a,b)$ if and only if ($a<2b+1$ and $a\equiv 2 \bmod 6$) OR ($a-b=2$ and $a\equiv 2 \bmod 6$) OR ($2a-3b>5$ and $2a+b\equiv 3 \bmod 6$).

Is there some similar characterization known when the language can contain only some fixed, bounded number of non-zero characters?

For example, for which $R$ is $\{0^a10^b10^c\mid R(a,b,c)\}$ context-free?

Related: I've discovered that this topic has been studied a lot for primitive words, see Kaszonyi-Katsura: Some new results on the context-freeness of languages.

$\endgroup$
  • 1
    $\begingroup$ A necessary condition is that for each $L = \{0^a10^b10^c\mid R(a,b,c)\} \in CFL$, $\{ \langle a, b, c \rangle \}$, must be a semilinear set: apply closure under inverse homomorphism $0 \to \{s_a,s_b,s_c\}$ where $s_a, s_b, s_c$ are three new symbols, intersect with the regular $\{ s_a^*1s_b^*1s_c^* \}$ and apply Parikh's theorem. And clearly also $\{ \langle a + b, c \rangle\}$, $\{ \langle a + c, b \rangle \}$, $\{ \langle a, b + c \rangle \}$, $\{ \langle a + b + c\rangle \}$ must be semilinear. The same argument is valid for more "fixed" symbols. $\endgroup$ – Marzio De Biasi Jan 13 at 22:49
  • 1
    $\begingroup$ ... another condition (probably provable from the same Parikh's theorem) is that $R$ cannot contain cross-serial dependencies $\{ \langle a,b,f(a),f(b)\rangle\}$ (as long as $\{a\},\{f(a)\}, \{b\}, \{f(b)\}$ are not finite) $\endgroup$ – Marzio De Biasi Jan 13 at 23:53
  • 3
    $\begingroup$ Are stratified sets what you're asking for? Ginsburg and Spanier have you covered if that's the case—see Ginsburg's book "The Mathematical Theory of CFL" and the chapter on bounded languages. $\endgroup$ – Michaël Cadilhac Jan 14 at 0:08
  • 2
    $\begingroup$ @Michael Exactly, Theorem 5.4.2 on page 162! Would you convert your comment to an answer? $\endgroup$ – domotorp Jan 14 at 9:41
  • $\begingroup$ @Michael I've also added this to Wikipedia, I would be grateful if you could check that I didn't make any mistakes: en.wikipedia.org/wiki/… $\endgroup$ – domotorp Jan 14 at 10:39
5
$\begingroup$

What you're looking for is an old result of Ginsburg and Spanier actually related to one of the oldest open questions of the field. See Ginsburg's book The Mathematical Theory of CFLs.

Defs. A linear set is a set of the form $\vec{v} + P^*$ where $\vec{v} \in \mathbb{N}^k$ and $P$ is a finite set of such vectors ($P^*$ denotes all linear combinations of the vectors in $P$). A linear set is stratified if :

  1. All the vectors in $P$ have at most two nonzero components;

  2. For all $\vec{x}, \vec{y} \in P$, the nonzero positions of $\vec{x}$ and $\vec{y}$ are not interleaved (this is related to the fact that $a^ib^ic^jd^j$ is CFL but not $a^ib^jc^id^j$).

Theorem. Let $w_1, \ldots, w_k$ be some words. Any CFL $L \subseteq w_1^*\cdots w_k^*$ can be written as $L = \{w_1^{i_1}\cdots w_k^{i_k} \mid (i_1, \ldots, i_k) \in R\}$ where $R$ is an union of stratified sets. Somewhat conversely, any language of that form with $R$ a union of stratified sets is a CFL.

Naturally, there are languages that are CFL that can be written in the previous way with $R$ being quite arbitrary—e.g., with $w_1=w_2=a$ and $R = \{(2^i, j)\}.$ However, if for instance all $w_i$'s are different letters, then $R$ has to be a union of stratified sets for $L$ to be a CFL.

As for the open question I mentioned before, the following problem is not known to be decidable:

  • Given: A finite union of linear sets
  • Question: Is this set presentable as a finite union of stratified sets?
$\endgroup$
  • $\begingroup$ Wow. Does any modern monograph/textbook treat this theorem, stratified linear sets, or this open problem? There seems to be quite some "abandoned stuff" in formal language theory. Which is of course natural as the field matures - from what I've read, AFL theory was a mainstream line of research in TCS in the 1970s. $\endgroup$ – Hermann Gruber yesterday

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.