World's most popular travel blog for travel bloggers.

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

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

Asked By : Elimination
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 :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback