Is the decision problem "Does a given context free grammar generate an infinite number of strings" decidable? In order to test whether a context free grammar generates an infinite number of strings or not, we can write a program that would test this but would not halt. So it should be undecidable. Is this so?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ No, your argument doesn't work. There could be some other way of approaching the problem which works better than the naive algorithm you describe. Think about the situation for regular languages, where such a shortcut does exist. $\endgroup$– Yuval FilmusCommented Jan 31, 2016 at 7:59
-
5$\begingroup$ Hint: are you familiar with the pumping lemma for CFGs? Try to follow its proof, and draw a connection to your problem. $\endgroup$– ShaullCommented Jan 31, 2016 at 8:00
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
Let $G$ be a context free grammar, and let us assume that it is in Chomsky normal form. If it's not, we'll convert it first. An important property of this normal form is that the only way to derive the empty word is with the single rule $S_0\to \epsilon$ (where $S_0$ is the initial variable, which cannot be derived from other variables).
Thus, any other derivation adds some non-trivial part to a word.
Now, let $n$ be the number of variables in the grammar, and let $k$ be the maximal length on the right-side of a derivation rule. That is, $A\to B_1\cdots B_k$ is the maximal length. We are going to show the following theorem:
$G$ generates an infinite word iff it generates a word of length at least $k^{n+2}$.
Consider some word $w$ generated by the grammar, and a derivation tree for it. The derivation tree has branching factor of at most $k$, and thus it needs to be of height at least $\log_k |w|$ in order to derive $w$.
Take a really long word $w$. Just how long? take $w$ of length $k^{n+2}$. Then, every derivation tree of $w$ requires at least height $\log_k(k^{n+2})=n+2$. That means that there is some path in the tree of length $n+2$, and on this part there is some variable that repeats (since there are only $n$ variables). We can assume that the derivation from this variable derives other things besides itself, otherwise we can shorten the tree.
Now, you can "pump" the word $w$ to infinitely many other words that are generated, by repeating the subtree of the variable that derives itself.
If this sounds complicated, take a look at the pumping lemma, it's the same idea.
So now what? Well, take your grammar, and "remove" from it all words of length less than $k^{n+2}$ by intersecting it with a regular language of all words of length at least $k^{n+2}$, and check if the resulting grammar is non-empty. If it is, the original grammar generated an infinite language, and otherwise - a finite language.
-
$\begingroup$ sounds about right but it would be helpful to phrase this in mathematical language/ proof ie in the form "CFL has infinite strings iff ... [x]" $\endgroup$– vznCommented Jan 31, 2016 at 16:41
-
1$\begingroup$ @vzn - I added a more formal statement. $\endgroup$– ShaullCommented Jan 31, 2016 at 16:48
-
$\begingroup$ "We can assume that the derivation from this variable derives other things besides itself, otherwise we can shorten the tree." Could you please expand on this? Also, when you say $n$ variables in the grammar, that includes both terminals and nonterminals? If that is the case, then I'm guessing: there is a path from the root of this tree to some leaf and this path has a length of $|n + 2|$. Because this length is greater than $n$, there must be some variable that are repeated along the path (not necessarily one after the other). This particular repetition can be pumped. Am I getting it right? $\endgroup$ Commented Jan 12, 2021 at 10:47
-
$\begingroup$ By "variables" I only count the non-terminals. In Chomsky normal form, terminals are only derived in a single rule, with a single terminal at a time. As for the derivation tree: if you have a "string" somewhere in the tree, i.e. of the form S->A->B->S, then you can shorten it, since you just had S deriving S and nothing else. So I mean we start by getting rid of these. $\endgroup$– ShaullCommented Jan 12, 2021 at 10:53
$\begingroup$
$\endgroup$
Without loss of generality¹, assume that the input grammar $G$ does not have $\varepsilon$-rules² and is in reduced form. That is,
- every non-terminal appears in at least one derivation (starting from the initial non-terminal), and
- every non-terminal produces at least one terminal string.
Then, $L(G)$ is infinite if and only if there is a non-terminal $A$ so that $A \Rightarrow^* \alpha A \beta$ for some $\alpha \cdot \beta \in (N \cup T)^+$.
Sketch of proof: For one direction, we have that $L(G)$ is infinite. Assume there was no such non-terminal; then there are only finitely many derivations by the pigeon-hole principle, which is a contradiction.
For the reverse, we have that there is such a non-terminal. Then, we know that $A$ can be derived to $\alpha^i A \beta^i$ for all $i \in \mathbb{N}$, and all these are distinct and derive to distinct terminal strings. Hence, $A$ alone generates an infinite set of substrings of strings in $L(G)$; therefore, $L(G)$ is infinite as well.
It's obvious that this criterion can be decided algorithmically; check for cycles of weight³ $> 0$ in the (multi-)graph made up of non-terminals as nodes, edges from $A$ to $B$ if $B$ appears on a right-hand-side of a rule for $A$, and weights are the number of terminals generated by these rules. Hence, the given problem is decidable.
- We know that there is such a grammar for every context-free language; there are even effective procedures for reducing grammars and removing $\varepsilon$-rules.
- Except maybe $S \to \varepsilon$ iff $\varepsilon \in L(G)$, and then $S$ can not appear on the right-hand side of any rule.
- If we eliminate chain rules $A \to B$ as well (a standard exercise), any cycle suffices.