How we decide for a given context free grammar generate an infinite number of strings?

Question

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 .

Answer 1

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

Answer 2

One way of determining whether a given context-free grammar $G$ produces an infinite language is this:

• Find a grammar $G^+$ with $L(G^+) = L(G)$ such that $G'$ has no rules on the form $A \to \varepsilon$ or $A \to B$ where $A$ and $B$ are any non-terminals. (Implication: for any derivation $\alpha \underline{A} \beta \Rightarrow \alpha \gamma \beta$ we have $\lvert \alpha A \beta \rvert < \lvert \alpha \gamma \beta \rvert$ unless $\gamma$ is a single terminal.)

• Find a grammar $G'$ with $L(G') = L(G^+)$ such that all non-terminals $A$ derive some string and $S \Rightarrow^* \alpha A \beta$ for some $\alpha$ and $\beta$ and which also has the above property of $G^+$.

• Construct a graph with an edge from $A$ to $B$ whenever $B$ occurs on the right-hand side of a rule $A \to \alpha B \beta$.

($\alpha$ and $\beta$ are arbitrary strings of terminals and non-terminals.)

If the graph has a cycle, the language is infinite. Otherwise not.

Proof(ish):

From cycle to infinity: as a consequence of the properties of $G^+$, any derivation $A \Rightarrow^* \alpha A \beta$ implies $\lvert \alpha \beta \rvert > 0$. In other words, each trip through the cycle makes the sentential form longer, and also nothing will make it shorter. The cycle can be gone through as many times as you like, and by the properties of $G'$ the cycle can be reached from $S$ and reaching it means you will eventually generate a string. Hence strings of an infinite number of different lengths can be generated. Strings of different lengths are different, hence the language has infinitely many strings.

From acyclic to finite: if there is no cycle, sort the non-terminals topologically. Let $A$ be any non-terminal with no out-edges, i.e. all right-hand-sides of production rules consist only of strings of non-terminals. Replace every occurrence of $A$ in some other right-hand side with the union of all strings $A$ can generate (so if $A \to a \mid b$ and $B \to Ac$ then when done $B \to ac \mid bc$) and remove $A$ from the grammar. It will still be acyclic, but shorter by one non-terminal. Repeat this until it consists only of $S$, which will have non-recursive production rules, i.e. its rules will just be a finite list of strings the language can generate.

Resources:

For the construction of $G^+$, apply the UNIT and DEL steps; see also my favorite definition of the DEL step. For construction of $G'$, see useless variable removal.