How to find whether a grammar's language is finite or infinite?

Problem Detail: 

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?

Asked By : Dana

Answered By : Yuval Filmus

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?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23367