Let S(n) be a set of n strings, where n 1. Each string in S(n) consists of k a’s
ID: 3814219 • Letter: L
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
using pseudo code or whatever
Explanation / Answer
I am writting pseudo code:
fun setn(n)
{
if n ==1{
return { ab }
}
else if n ==2
{
return { ab, aabb }
}
else
return setn(n-1) union setn(n-1)
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.