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)$).

  • The first answer here may be of use. – Eric Towers Aug 15 '17 at 21:24
  • @EricTowers I edited my question and followed your clue. Could you look on it ? – Haskell Fun Aug 16 '17 at 12:02
  • Even if this solution is ok, it is hard to show that determining of emptiness of CFG is p complete – Haskell Fun Aug 16 '17 at 12:31
  • Okay... How about a different sort of hint. Do you know Greibach normal form and a method to convert a CFG to GNF? This allows you to express your grammar as a (useful for your purpose) digraph. What would a cycle in this digraph tell you? – Eric Towers Aug 20 '17 at 0:54
  • OK, I consider this hint later. However, what about my solution (after edition) ? – Haskell Fun Aug 20 '17 at 10:00
up vote 0 down vote accepted

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...

  • That's incredible, but before I invented this trick which you show above. However, only now I managed (I believe) to solve it. We convert HORNSAT clauses as you show. Now, $\phi \in HORNSAT$ is satisfable iff grammar generates infinite language. Obviously, we can think about clauses as: $u \implies p \vee q \vee \cdots \vee t$ - in other words negations dont matter. Then, we have productions introduced directly from formula and additionally each variable $t\to [true]$ where $[true]$ is terminal - one symbol. We should note that [false] don't exists (it make no sense). – Haskell Fun Aug 21 '17 at 18:27
  • If in each path of grammar we got a word then this word if finite sequence of $[true]$. In case of infinite grammar we have some cycle (without cycle language is not infinite). It means that some variables are in conflict, then assigment doesn't exists. Am I correct ? – Haskell Fun Aug 21 '17 at 18:38
  • @HaskellFun : That is exactly the right plan and I think you're looking at the right details to execute that plan. – Eric Towers Aug 21 '17 at 23:51
  • Ok, after my work I work out lacking details. Could you hide under spoiler solution in nutshell ? To finish this thread. In case of my doubts I can look under spoiler, however I think that it can be only in order to make sure that I done exercise. – Haskell Fun Aug 22 '17 at 4:29
  • I can't understand some thing: After all, we can assign all variables to $0$ and we have the same $1s$ (because negations) and then such hornat clause is satisfable in obvious way – Haskell Fun Aug 22 '17 at 17:23

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.