1,730 views
2 votes
2 votes
S-->aSa|bSb|a|b|epsilon

for above CFG find the total no of strings generated whose length is less than or equal to 10 [excluding the empty string]

?

1 Answer

Best answer
5 votes
5 votes

Length 1 String -- a,b              --(2)
Length 2 String --  aa,bb          --(2)
Length 3 String -- aaa,bbb,aba,bab  -- (4)
Length 4 String -- aaaa,bbbb,abba,baab  ---(4)

.
.
.

Similarly following pattern till Length 10
We get ==>   2*2 +2*4 +2*8 +2*16 +2*32
            ==>    4+ 8+16+32+64
           ==> 124


Ans :124

selected by

Related questions

0 votes
0 votes
0 answers
1
aaru14 asked Nov 18, 2017
327 views
https://gateoverflow.in/?qa=blob&qa_blobid=13192646339913379886please someone exaplain ?
1 votes
1 votes
0 answers
2
aaru14 asked Nov 13, 2017
215 views
S >aSb|SS|epsilonL={w|w belongs {a,b}* and a(v)>=b(v), where v is any prefix of w} (propery balanced parenthesis) plz someone tell me what does it mean am not getting???
2 votes
2 votes
0 answers
3
aaru14 asked Nov 13, 2017
1,945 views
L={a^n b^n a^n |n=1,2,3.........} is an example of a language that is a)context freeb)not context freec)not context free but whose complement is CFd)context free but whos...