# Tag Info

### List of nice non-context-free languages

If I had to summarize the capabilities/limitations of CF languages I would say: they can pair "things" but two distinct pairings cannot overlap they can "count" but only linearly (...

### List of nice non-context-free languages

Two simple examples of non-context-free languages are PRIMES $= \{ a^p \mid p \text{ prime} \}$ and POWERS $= \{ a^{2^n} \mid n\ge 0 \}$. One can prove that they are not context-free by the pumping ...
• 4,561

### Finding a minimal context free grammar that recognizes a finite set of strings of bounded length

The following inapproximability result is known (Theorem 17 in Gruber/Holzer/Wolfsteiner, DLT 2018): Given a context-free grammar of size $s$ generating a finite language $L$, it is impossible to ...
• 6,625
Accepted

### Modify DCFG to enforce length limit

A partial answer: The number of productions needed by a (not necessarily deterministic) context-free grammar generating $L\cap \Sigma^{\le N}$ in the worst case is $\Theta(N^2)$, as given in Theorem 4 ...
• 6,625

### List of nice non-context-free languages

You can group non-context-free languages into groups depending on what lemma you use to show that they are not context-free. Noam already mentioned the pumping lemma in his answer, let me mention the ...
• 14.1k
The following is kind of a variant of the examples already given, but I believe it is sufficiently different that is worth mentioning. $L=\{a^n b^m a^n b^m\mid n,m\in \mathbb{N}\}$ Proof by using the ...