Context-free Grammar ϵ-Membership (CFGϵmem)
Category: Formal Languages
Input
A context-free grammar $G = (N, T, P, S)$.
Problem
Is $\epsilon \in L(G)$?
Status
$\P$-complete (Goldschlager [1], Jones and Laaser [2]).
Remarks
The reduction to show hardness is from MCVP, a variant of CFGempty.
References
- L. M. Goldschlager (1981). ϵ-productions in context-free grammars.
- N. D. Jones and W. T. Laaser (1976). Complete problems for deterministic polynomial time.
- Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem A.7.4.