1
$\begingroup$

For a grammar $G$, why is the problem of whether $L(G)=\emptyset$ is undecidable? I'm confused as, for recursive languages there exists a Turing machine which will halt every time and give an answer(accepted or rejected) for each and every string input. So we can decide whether it accepts strings or not.

$\endgroup$
5
$\begingroup$

For any particular string $x$, the question of whether $x \in L(G)$ is decidable (if G is not unrestricted), and that's what you've described.

However, the problem you've given is not whether a particular string is in $L(G)$, but whether any string is in $L(G)$. There are infinitely many strings to try. We can test each one in sequence, and if it is in $L(G)$ then we know it is not empty. But if $L(G)$ is empty, how do we know when to stop? There are infinitely many strings, so we never know if the next string is the one that's in the language. So we never know when to stop.

That said, the decidability greatly depends on what type of language/grammar $G$ is. For context-free languages, this is decidable, since we can make a pushdown automaton and perform a search to see if an accepting state is reachable. But for other, more complicated types of languages this may very well be undecidable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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