Show that the following language is decidable

decidability

$E_{cfg}=\{ \langle G \rangle \mid G \text{ is context-free grammar}, \ L(G)=\emptyset \}$

I think the following algorithm should work:

  1. Test whether or not the input $w$ codes a cfg. If not, reject.

  2. When $w$ codes a cfg, apply "output algorithm" on cfg:

    if algorithm outputs a word, break after the first word and reject

    if algorithm terminates without output, accept.

Is this algorithm ok? How would I prove that step 1) is acutally doable? Do you think I'd have to specify the output algorithm for the cfgs further?

Thanks..

Best Answer

For sure you can effectively tests if a string codes a CFG (of course, you have to know how this code is built, but you can assume that the grammar is given in some "normal" form).

The real problem is with the second part: your "algorithm" do not decide if the recognized language is empty, and this because it is actually a semi-algorithm, as it does not halt if the language is empty (you can have an infinite derivation starting from the axiom that never reach a terminal symbol). Anyway, the problem is decidable, this is a sketch of a decision procedure:

Let $G$ the CFG and $S$ its axiom, then:

  1. Mark all terminal symbols in $G$

  2. Mark any nonterminal $A$ such that $G$ contains a rule $A \rightarrow u_1\ldots u_n$ and each symbol $u_i$ has already been marked

  3. Repeat 2. until no new nonterminal gets marked

  4. If the axiom $S$ of $G$ is marked, then the language is not empty, otherwise it is empty.

From the finiteness of the set of symbols it follows that the procedure always halts (you cannot repeat 2. two times doing nothing). Moreover, this procedure solves a more general problem: namely, whether from a nonterminal a string of terminals is derivable.

Related Question