[Math] How we decide for a given context free grammar generate an infinite number of strings

automatacomputational complexitycontext-free-grammardecision-theory

Consider the following decision problems:

(P1) Does a given finite state machine accept a given string?

(P2) Does a given context free grammar generate an infinite number of strings?

Which of the following statements is true?

  1. Both (P1) and (P2) are decidable
  2. Neither (P1) nor (P2) is decidable
  3. Only (P1) is decidable
  4. Only (P2) is decidable

My Try:

Somewhere it explained as following:
Statement (P1) is the membership problem of regular language , which is decidable problem . We need to find a string end with final state of DFA or not ? No problem here .

For the statement (P2) , I'm confused really . Since ,

  1. It is undecidable : Determining if a context-free grammar
    generates all possible strings, or if it is ambiguous.

  2. Decidable/undecidable : Does a given context free grammar generate
    an infinite number of strings?

This explained in given link : check if the CFG generates any string of length between $n$ and $2n-1$. If so, L(CFG) is infinite, else finite.So above problem (2) is decidable .

I'm not getting above explanation of this problem :

How we decide for a given context free grammar generate an infinite number of strings ? Can you explain little bit more ,please .

Best Answer

IF $L$ is a CFL, the Pumping Lemma for CFLs tells us that for some integer $n \ge 1$, if $s \in L$ and $|s| \ge n$, then $s$ can be written as

  1. $s = uvwxy$ where
  2. $|vwx| \le n$,
  3. $v\neq \varepsilon$ or $x \neq \varepsilon$, and
  4. for all $k\ge 0, uv^kwx^ky \in L$.

If some $s\in L$ has length $n \le |s| < 2n$, then $L$ is infinite: for some $u,v,w,x,y$ as in the Pumping Lemma, $L$ then contains all strings $uv^kwx^ky$ for $k\ge 0$. Because at least one of $v,x$ is nonempty, these strings are all distinct.

Conversely, suppose $L$ is infinite. Then $L$ contains strings of length $\ge n$. Suppose $s\in L$ has length $|s|\ge n$. Then $s = uvwxy$ as in the Pumping Lemma. If $|s|\ge 2n$, then we can "pump downward": $s' = uwy = uv^0wx^0y \in L$ is a strictly shorter string, which by 2. still has length $|s'|\ge n$. ($|s'| = |s| - |vx| \ge |s| - |vwx| \ge |s| - n \ge n$.)

If $s'$ is still of length $\ge 2n$ then we can do it again, to obtain yet another, even shorter string $s''$ of length $\ge n$. Eventually we obtain a string $\overline{s}$ whose length is $< 2n$ and $\ge n$.

Related Question