Context-free Grammar Empty (CFGempty)

Input

A context-free grammar $G = (N, T, P, S)$.

Problem

Is $L(G)$ empty?

Status

$\P$-complete (Jones and Laaser [1], Goldschlager [2]).

Remarks

Same reduction as for CFGmem suffices, but it may also be reduced from MCVP [3].

Note, this reduction and the one for CFGinf, have no $\epsilon$-productions yet remain complete. The original proof of Jones and Laaser reduced GEN to CFGempty. Their proof used the reduction for CFGmem, and instead checked if $L(G)$ is empty [1].