0
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ What makes you so sure this language is context-free? $\endgroup$
    – Nathaniel
    Nov 11, 2022 at 16:05
  • $\begingroup$ @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. $\endgroup$ Nov 11, 2022 at 16:09
  • $\begingroup$ @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 $\endgroup$ Nov 11, 2022 at 16:09
  • 2
    $\begingroup$ 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. $\endgroup$
    – Nathaniel
    Nov 11, 2022 at 16:19

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

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

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