how to come up with a solution of finite or infinite language using context free grammer?

Question

I am trying to come up with a solution of finite or infinite language using context free grammer.

I have these grammers to find if it's a solution of finite or infinite language

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 to generate words like this but how do find if its finite or infinitive language ?

Answer 1

One method is to, first, transform the grammar into Chomsky Normal Form, after having deleted non-yielding and unreachable symbols (yours is quite close as is now and don't need to change it, but I'm just saying for the general case). Then construct a directed graph as follows:

• Make a vertex for every non-terminal symbol of the grammar.
• Put edges $(A,B)$ and $(A,C)$ for each production rule $A\to BC$.

If you form a DAG, then the language is finite. Else, if the graph has a circle, then the language is infinite.