Register

madeeasy work book

2,404 views
2 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 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
Voting & Accepting an answer helps improve the community
← Previous · Relational AlgebraNext → · Test Series
← Previous in category · micheal sipser bookNext in category → · Where to get PPT for...
Position:
Show:

Related questions

0 0 votes
0 0 answers
561
561 views
aaru14 asked Nov 18, 2017
561 views
madeeasy work book
https://gateoverflow.in/?qa=blob&qa_blobid=13192646339913379886please someone exaplain ?
1 1 vote
0 0 answers
426
426 views
aaru14 asked Nov 13, 2017
426 views
madeeasy work book
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 2 votes
0 0 answers
2.3k
2.3k views
aaru14 asked Nov 13, 2017
2,349 views
madeeasy work book
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...
2 2 votes
1 1 answer
798
798 views
aaru14 asked Nov 11, 2017
798 views
madeeasy work book
which of the following is decidable?1)for some input if an arbitrary TM makes 5 moves.2) whether an arbitary TM halts within 5 steps3) whether an arbitary TM prints some ...