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.

Improve this question
$\endgroup$
5
  • 2
    $\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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 10:39

1 Answer 1

Reset to default
6
$\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?
Improve this answer
$\endgroup$
1
  • $\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
    Jan 20, 2019 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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