retagged by
511 views

1 Answer

3 votes
3 votes
Both the grammars will produce a finite language .Since a language is infinite if we have recursion on start symbol of a language i.e. recursion should be applied on start symbol directly or indirectly.But no such recursion on S which is the start symbol for both of the above grammars.

Hence C) should be the correct option.

I would like to add one fact here that not every recursion leads to infinite language.

e.g. S --> ab

   A --> aA

So if we consider S as the start symbol in the above grammar then A has no role in forming strings of the language ,or in other words A has no role in sentential form of a string.Hence the given language only produces {a} and hence is finite and as we can see the recursion due to A is useless.

Related questions

0 votes
0 votes
2 answers
1
1 votes
1 votes
1 answer
2
0 votes
0 votes
3 answers
3
Anmol Verma asked Nov 30, 2016
2,266 views
S->AbaCA->BCB->b/epsilonC->D/epsilonD->d I want to know that will A contain epsilon as B and C both are null variables???(In Elimination of epsilon-production)
3 votes
3 votes
1 answer
4
himanich asked Jun 22, 2016
606 views
If language $L=\{a^n b^n \mid n \geq 0\}$, then language $L^2$ is given by$\{a^{2n} b^{2n} \mid n \geq 0\}$$\{a^n b^n a^n b^n \mid n \geq 0\}$$\{a^n b^n \mid n \geq 0\}$$...