5
$\begingroup$

I have this context-free grammar and I want to find out whether its language is finite or infinite.

S -> XY|bb  Step 1
X -> XY|SS  Step 2
Y -> XY|SS  Step 3

So I would do

S -> XY            From step 1
S -> YYY           From step 2
S -> SSYY          From step 3
S -> SSSSY         From step 3
S -> SSSSSS        From step 3
S -> bbSSSSS       From step 1
S -> bbbbSSS       From step 1
S -> bbbbbbSSS     From step 1
S -> bbbbbbbbSS    From step 1
S -> bbbbbbbbbbS   From step 1
S -> bbbbbbbbbbbb  From step 1

bbbbbbbbbbbb 

So I know how to generate words like this but how to find out whether the language is finite or infinite?

$\endgroup$
2
  • 3
    $\begingroup$ Can you generate infinitely many words? If so, the language is infinite. In this case, you have $S \rightarrow^* SSSS$, which suggests that the language is infinite. $\endgroup$ Commented Apr 2, 2014 at 20:43
  • $\begingroup$ math.stackexchange.com/a/1891462/14578 $\endgroup$
    – D.W.
    Commented Jun 3 at 17:55

4 Answers 4

9
$\begingroup$

A language is infinite if it can generate infinitely many words. In order to prove that a language generated by a grammar is infinite, you need come up with some infinite list of words generated by the grammar. Proving that the language is finite is slightly more messy—you need to make a list of all possible derivations, and show that all of the terminate.

In your case, you have the derivation $S\to^*SSSS$, which suggests that the language is infinite. Can you come up with an infinite list of words generated by this grammar?

$\endgroup$
6
  • $\begingroup$ so lets say I don't have S -> SSSS, but I have S -> XY, S ->bY, S -> ba etc for example does that mean that it is finite ?...sorry I am just trying to figure out the difference here... $\endgroup$
    – Dana
    Commented Apr 2, 2014 at 21:01
  • 1
    $\begingroup$ A grammar generates a finite language if you can only generate finitely many words. That is all there is to it. Here is an example of a finite grammar: $S \to AB|a$, $A \to B|BB|BBB|BBBB|b|c$, $B \to a|ab|abc$. $\endgroup$ Commented Apr 2, 2014 at 21:11
  • $\begingroup$ Having "non-empty" recursion is one necessary condition, but you also need $S \to^* w$ for some word $w \in \Sigma^+$. (I think something like that is necessary and sufficient.) $\endgroup$
    – Raphael
    Commented Apr 3, 2014 at 6:28
  • $\begingroup$ This is a good explanation but not a good process, you didn't show how this can be done (it's not always so intuitive). One way to find out whether a context-free grammar is infinite or not is to first convert to Greibach Normal form, then check for any cycles in the grammar. If there are any cycles then it's infinite, otherwise it's finite. $\endgroup$ Commented Apr 3, 2014 at 19:32
  • $\begingroup$ @Spencer You're right, one can come up with an algorithm, probably even without converting to Greibach normal form. Perhaps you could write the details in a different answer to this question. $\endgroup$ Commented Apr 3, 2014 at 20:07
6
$\begingroup$

The only way a finite system (grammar) can generate an infinite set of words is by repeating stuff: you start at $S$ and keep expanding until you hit a non-terminal that you've already expanded. So now you can just copy the sub-tree corresponding to that symbol and paste it. You can do this forever so it must be that the grammar generates infinitely many words.

You can use a directed graph to represent a context-free grammar: think of the grammar specification as being an adjacency list of some graph (In the first rule, there is an edge from $S$ to $X$ and from $X$ to $Y$ and so on). Now, the grammar generates an infinite set if and only if the graph is cyclic (this needs proof). A technicality is that the cycle should generate something other than the empty word. This gives a general procedure for deciding whether a grammar generate an infinite set of words or not.

The graph corresponding to your example looks like:

enter image description here

There are lots of cycles. $S^*$ ($(bb)^*$ is a subset of the language that the grammar generates) is one example.

$\endgroup$
5
  • $\begingroup$ Would the grammar with rules S-->S|X|b, X-->S|X|Y, Y-->S|X give a different graph. $\endgroup$
    – babou
    Commented Apr 4, 2014 at 9:05
  • $\begingroup$ @babou No! But it generates an infinite set. $\endgroup$
    – mrk
    Commented Apr 4, 2014 at 11:50
  • $\begingroup$ Actually it generates only one word: "b". But I do not understand why the graph should be different. Can you give one example where it differs: an arc that will be missing, and why. $\endgroup$
    – babou
    Commented Apr 4, 2014 at 12:08
  • $\begingroup$ Oh! No answers your question: same graph. Nice catch but I mentioned that it needs proof. $\endgroup$
    – mrk
    Commented Apr 4, 2014 at 12:13
  • 1
    $\begingroup$ @babou The logic is correct but the grammar should be in CNF because the grammar you have mentioned is not in CNF. you should first eliminate unit productions and then convert it to CNF . The grammar in CNF is just S->b because after unit production elimination X and Y are because they are not reachable by S. $\endgroup$ Commented Oct 15, 2015 at 12:37
5
$\begingroup$

The language is infinite iff its grammar can generate an infinite number of words, or equivalently iff a recognizing automaton can recognize an infinite number of words.

This is something that you have to prove.

For that purpose you can rely on some facts.

  • a language is infinite if and only if contains words of unbounded length, i.e. longer than any size you may choose.

    (Useful and easy exercise: prove that the total number of words of size less than some integer $n$ built on a finite alphabet $\Sigma$ is always finite. - this proves the above statement)

    This tells you two things

    • that if you can show that the language contains words of unlimited size, it is indeed infinite.
    • that you can always count on that property to prove language infinity
  • To prove that words can have unlimited size, you must use an induction proof. And, when using a grammar definition of the language, it will have to be based on non-terminals as they are the only part of a derived string that can be replaced by something longer.

For example, if the initial symbol derives on a string that contains it plus other symbols, including a terminal, and only non-terminal that derive on a terminal word ... the you may think on using that for an induction proof.

Well ... what about trying?

And try to think why I specify these constraints. (remember, the words of the language contain only terminals)

By the way, the recursion must sometimes be on another non-terminal than the initial one (S). But it will do in your case.

$\endgroup$
1
  • $\begingroup$ THank you..it makes more sense now, this was a little confusing $\endgroup$
    – Dana
    Commented Apr 2, 2014 at 23:52
3
$\begingroup$

I recall from the 1960's a technique for at least some classes of formal grammars for finding cycles (loops generating an infinite language ) in a grammar. A Boolean matrix is created for all rules or productions in the grammar. All terminals and non-terminals are listed as the vertical side of the matrix and the horizontal side of the matrix. There are zeros in the matrix where vertical side of the rule does not directly produce a symbol across the horizontal side. There ones where the left part (row title) directly produces the right part (column title)

This captures all the direct transitions. This matrix is multiplied times its transpose. The martix multiplication is simplified by the use of Warshall's algorithm. The result is the reflexive transitive closure of the grammar. The grammar is cycle free if the right to left diagonal of the resulting matrix is all zeros.

$\endgroup$
2
  • $\begingroup$ This approach requires a bit of care. The grammar S -> a | T, T -> T is finite but not cycle free, so the procedure above will give the wrong answer on that grammar. It also gives the wrong answer for the grammar S -> a | U, U -> b | U. It's possible that something along these lines might work if you first pre-process the grammar somehow but it's not clear to me exactly what pre-processing is necessary and sufficient, nor how to prove that the resulting method is correct for all grammars. $\endgroup$
    – D.W.
    Commented Mar 27, 2017 at 17:53
  • $\begingroup$ In fact we can say more: L. Valiant showed (in General context-free recognition in less than cubic time) that Boolean matrix multiplication can be used for parsing CFGs, yielding the asymptotically fastest (although not practical) CFG parsing algorithm known. One may now ask: does parsing require matrix multiplication? Maybe one can come up with something better/faster. L. Lee (in Fast context-free grammar parsing requires fast Boolean matrix multiplication) then shows that that's not the case: the fast CFG parsing requires fast Boolean matrix multiplication. $\endgroup$ Commented Mar 27, 2017 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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