Show that checking if context free grammar generates infinite language is P-complete with logspace reduction

Question

Show that following problem is P-complete in respect to logspace reduction in sense of Karp
Given: context free grammar $G$
Decide: Check if $G$ generates infinite language

Obviously this problem is in $P$ - it is sufficient to check if it contains cycle in derivation (and this derivation is non empty - contains some terminals). It is very easy to give polynomial algorithm.

When it comes to $P-completness$ I am hopeless. I have spent a hours to try reduce HORNSAT (which is $P$-complete) to problem in exercise.

Can you give me some clues ?

Edit after comments
We reduce checking if grammar generates empty language to our problem.
Let $G$ will be grammar ($S$ is starting symbol):
$$S\to A|B|C$$ we transform it to $G'$
$$S\to SA|SB|SC|A|B|C$$
Now, let's assume that $S$ generates some word (in other words $L(G)\neq \emptyset$).

Then $G'$ generates inifnite language, because we can arbitrarily many times repeat rule $S\to SA$: $$S\to SA \to SSA \to SSSA \to SSSSA \to BCCBA$$

Let assume that $G'$ generates infinite language. It means that $G'$ generates some word (so $L(G')\neq \emptyset$). So also $G$ generate some word - in other case $G'$ can't generate any word ($G'$ only repeat many times word from $L(G)$).

Answer 1

First, let's make sure we're all using the same definitions.

• CFG : context free grammar
• P-complete : the set of decision problems to which every member of P can be reduced. In this setting, we are using LOGSPACE reductions to embed arbitrary members of P into our problem.
• HORNSAT : The decision problem of determining whether a given a set of Horn clauses has a satisfying assignment of its boolean variables. HORNSAT is in P-complete.
• Horn clause : a disjunction with only one non-negated term. Equivalent to a conjunction implying the non-negated term and by contrapositive to the second implication shown below. \begin{align*} (\neg p \vee \neg q \vee \cdots \vee \neg t \vee u) &\iff (p \wedge q \wedge \cdots \wedge t \implies u) \\ &\iff (\neg u \implies \neg p \vee \neg q \vee \cdots \vee \neg t) \end{align*}

Next, we wish to show that the decision problem "given a CFG, $G$, decide whether the language generated by the grammar, $L(G)$, is infinite" is P-complete. you intend to do so by showing a LOGSPACE reduction of HORNSAT instances to instances of this decision problem.

So our question is: how do we encode Horn clauses as CFG production rules such that the resulting language of the CFG is infinite if and only if there is an assignment of values to the variables of the Horn clauses satisfying the clauses?

Since you've still pretty much asked for clues, ..., the last of the implications in the display above sure does look like a production rule...