Context-free Grammar Infinite (CFGinf)
Category: Formal Languages
Input
A context-free grammar $G = (N, T, P, S)$.
Problem
Is $L(G)$ infinite?
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.3.