2
$\begingroup$

I was referring to slide 4 of this, which states following:

It is decidable whether a given CFG accepts a non-empty language?

Then I was reading Intro to Automata theory book by Ullman et al. It states following:

Let $L_{ne}$ be the language of all codes for Turing machines that accept atleast one input string. $$L_{ne}=\{M | L(M)\neq \phi\}$$ $L_{ne}$ is not recursive.

Knowing that "not recursive" is same as "undecidable" and the functionality of Turing machine is expressed as a CFG, I feel that the problems in above two statements sound same and the statements contradicts each other in terms of their decidability claims. Thus, one of them must be wrong. However I also feel that I still miss something basic and both of them are non contradictory and equally true. But then what I miss?

$\endgroup$
3
$\begingroup$

The thing you missed is that Turing Machines are strictly more expressive than Context-Free Grammars. CFGs are as expressive as push-down automata (PDA, i.e. automata with one stack).

E.g. the language $L = \{a^nb^nc^n | n > 0\}$ cannot be expressed by CFG (or decided by a PDA), but can be decided by a Turing Machine.

So, for CFG, the emptiness problem is decidable, but somewhere on the way to Turing completeness, this property is lost.

$\endgroup$
  • $\begingroup$ Ahhhh I mistook CFG for unrestricted grammar...The functionality of TM can be expressed with the help of unrestricted grammar (of form $(V\cup T)^+\rightarrow(V\cup T)^*$), whereas PDA functinality is expressed as CFG (taking form $V\rightarrow(V\cup T)^*$). So I think I can say that "its decidable whether language accepted by a PDA is empty or not". Right? $\endgroup$ – anir123 Dec 20 '16 at 12:11
1
$\begingroup$

The solution is a bit subtle. Wikipedia says the following:

A CFG can be constructed that generates all strings that are not accepting computation histories for a particular Turing machine on a particular input

That means you can reduce the halting problem to the problem, "Does this CFG generate all strings?", but not necessarily to the problem "Does this CFG generate the empty language?".

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