# What context-free grammar recognizes a list of numbers 1 - N in order?

I'm looking for a context-free grammar that recognizes precisely the numbers 1 - N in order:

1,10,11,100 valid (numbers 1 - 4 in base-2)

1,1,10,11,100 invalid (duplicate 1)

1,10,100 invalid (missing 3)

10,1,11,100 invalid (has all numbers but 1 and 2 are not in the correct position)

I'm not sure where to start to create the grammar.

The closest I could come up with are these rules, which I believe recognize a list of N natural numbers (with no constraints to order or duplicates or missings).

S -> B
B -> B,B | 1A | 1
A -> AA | 1 | 0


A, B, S are non-terminals

1, 0, , are terminals

S is start symbol

What context-free grammar recognizes a list of numbers 1 - N in order?

• What makes you so sure this language is context-free? Nov 11, 2022 at 16:05
• @Nathaniel I'm not sure. I thought "if solvable in polynomial time, then there exists a context-free grammar for it" and you can recognize a sorted list of integers in polynomial time by incrementing a counter and comparing the items in the list to the counter after each increment, so I figured there must be a context-free grammar that does the same. Nov 11, 2022 at 16:09
• @Nathaniel "Context Free Grammar Membership – Given a context-free grammar and a string, can that string be generated by that grammar?" en.wikipedia.org/wiki/P-complete Nov 11, 2022 at 16:09
• The fact that the CFG membership problem is in $\mathsf{P}$ has nothing to do with the fact that any language in $\mathsf{P}$ is context-free. Nov 11, 2022 at 16:19

This language $$L$$ is not context-free, so there is no CFG generating it.

Indeed, suppose it is context-free, and let $$n$$ be the pumping length. Let $$u \in L$$ be a word of length $$\geqslant n$$ (for example $$u = 1, 2, …, n$$ in binary). The pumping lemma states that $$u$$ can be written $$u = vwxyz$$ such that:

1. $$|wxy| \leqslant n$$;
2. $$|wy| > 0$$;
3. for all $$k\geqslant 0$$, $$vw^kxy^kz\in L$$.

Suppose there is a decomposition $$u = vwxyz$$ verifying the first two points. Without loss of generality, suppose $$w\neq \varepsilon$$ (the same reasonning can be done if $$y\neq \varepsilon$$). Then:

• if $$w$$ contains two symbols ,, then $$w^2$$ will contain twice the same number, so $$vw^2xy^2z$$ contains repetitions so is not in $$L$$;
• if $$w$$ contains no symbol ,, then $$vw^2xy^2z$$ will skip some numbers (we made the integer where $$w$$ appears bigger), so it is not in $$L$$;
• if $$w$$ is exactly ,, then $$vw^2xy^2z$$ contains ,, so it is not in $$L$$;
• finaly, if $$w = w_1,w_2$$ with $$w_1$$ and $$w_2\in\{0,1\}^*$$, then $$vw^3xy^3z$$ will contain $$w_1,w_2w_1,w_2w_1,w_2$$, so it contains twice the number $$w_2w_1$$, so it is not in $$L$$.

In all cases, the decomposition does not satisfy the third item. By contradiction, we conclude $$L$$ is not context-free.