I have this context-free grammar and I want to find out whether its language is finite or infinite.S -> XY|bb  Step 1X -> XY|SS  Step 2Y -> XY|SS  Step 3So I would doS -> XY            From step 1S -> YYY           From step 2S -> SSYY          From step 3S -> SSSSY         From step 3S -> SSSSSS        From step 3S -> bbSSSSS       From step 1S -> bbbbSSS       From step 1S -> bbbbbbSSS     From step 1S -> bbbbbbbbSS    From step 1S -> bbbbbbbbbbS   From step 1S -> bbbbbbbbbbbb  From step 1bbbbbbbbbbbb So I know how to generate words like this but how to find out whether the language is finite or infinite?
How to find whether a grammar's language is finite or infinite?
formal languages;context free;formal grammars;proof techniques;induction
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?