Cheap and Secure Web Hosting Provider : See Now

Proving that a set of grammars for a given finite language is decidable

, ,
Problem Detail:

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\}$?

Answered By : Yuval Filmus

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$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43902

3200 people like this