Let S ( n ) be a set of n strings, where n 1. Each string in S ( n ) consists of

Question

Let S(n) be a set of n strings, where n 1. Each string in S(n) consists of k a’s followed by k b’s, where k n. For example:

S(1)

  =  

{ ab }

S(2)

  =  

{ ab, aabb }

S(3)

  =  

{ ab, aabb, aaabbb }

S(4)

  =  

{ ab, aabb, aaabbb, aaaabbbb }

Write a recursion that computes S(n) for any n 1. Hints: you may need to use string concatenation ‘’ and set union ‘’. You may also need string-set concatenation ‘’, which is defined as follows, where the ’s and ’s are strings.

{ 1, 2 ..., m }

  =  

{ 1, 2 ..., m }

{ 1, 2 ..., m }

  =  

{ 1 , 2 ..., m }

String-set concatenation is not in Rosen: I made it up. You are not allowed to use ‘‘set builder’’ notation to solve this problem

S(1)

  =  

{ ab }

S(2)

  =  

{ ab, aabb }

S(3)

  =  

{ ab, aabb, aaabbb }

S(4)

  =  

{ ab, aabb, aaabbb, aaaabbbb }

Explanation / Answer

int sgrammer( int n)

{ for (i=1;i<=n;i++)

{

str=pow("a".1);

printf("%s",str);

}

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.