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\}$?
Proving that a set of grammars for a given finite language is decidable
formal languages;computability;context free
Hint: Combine the following two properties of context-free grammars: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$.Given a context-free grammar $G$, there is an algorithm deciding whether $L(G) = \emptyset$.