Context-free Grammar Membership (CFGmem)

Input

A context-free grammar $G = (N, T, P, S)$ and a string $x \in T^\ast$.

Problem

Is $x \in L(G)$?

Definitions

Here, $N$ is the set of nonterminal symbols, $T$ is the set of terminal symbols, $P$ is the set of production rules, and $S$ is the start symbol.

Status

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

Remarks

The reduction to show hardness is from GEN. Goldschlager remarks it is the presence of $\epsilon$-productions in the input grammar that make the membership question difficult [2]. Lewis, Stearns, and Hartmanis’ $(\log n)^2$ space algorithm [3] and Ruzzo’s $\mathsf{AC}^1$ (hence $\NC^2$) algorithm [4] for general context free language recognition can both be modified to work with an $\epsilon$-free grammar given as part of the input. For a fixed grammar, unbounded fanin size $O(n^6)$ suffices [4].

Rytter shows context-free languages can be recognized on a cube connected computer in $O((\log n)^2)$ time using $n^6$ processors [5]. He also provides an $O(\log n)$ time $n^7$ processor COMMON CRCW- PRAM algorithm for the recognition of unambiguous context-free languages [6]. Klein and Reif give an $O(\log n)$ time $n^3$ processor CREW-PRAM algorithm for the recognition of deterministic context-free languages [7]. Dymond and Ruzzo give a somewhat simpler algorithm for this problem on the more restricted CROW- PRAM [8]. Kaji et al. prove Parallel Multiple Context-free Grammar Membership and Multiple Context-free Grammar Membership, which are problems involving generalizations of context-free grammars that are designed to model natural languages, are $\P$-complete [9].