Let the language $$L = \left\{ \langle G \rangle \ |\ L(G) = \{1,\ldots , 1000\}, \text{ G is a CFG }\right\}$$

Prove that $L \in R$.

Well, I think that for a start we need to check whether or not $L(G)$ is infinite, so we only need to check if there's a word $w\in L(G)$ such that $n \le \left|w\right|\le 2n$

Suppose $L(G)$ is finite. How can I validate that $L(G) = \{1,\ldots ,1000\}$?


Hint: Combine the following two properties of context-free grammars:

  1. Given a context-free grammar $G$ and a regular language $L$ (given by a DFA, say), there is an algorithm that constructs a context-free grammar $G'$ satisfying $L(G') = L(G) \cap L$.

  2. Given a context-free grammar $G$, there is an algorithm deciding whether $L(G) = \emptyset$.


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