- #1
mr_coffee
- 1,629
- 1
Hello everyone. I'm not sure if I'm doing this right or not. The problem asks:
Consdier the set of all strings of a's, b's, and c's.
a. make a list of all of these strings of lengths zero, one, two, and three that do not contain the pattern aa.
Okay so i have the following:
note e: stands for empty
length 0: e
length 1: a; b; c;
length 2: {a,b}, {a,c}, {b,c}, {b,b}, {c,c}
okay for length 2, I'm confused, do they want all possibe like for instance:
is {a,b} equal to {b,a}? like {1,2} would be equal to {2,1} if we are just talking about sets, order doesn't matter but I'm not sure if they are talking about sets or not...
Length 3: {aba, abb, abc, aca, acb, acc, bab, bac,
bba, bbb, bbc, bca, bcb, bcc, bcab, cac, cba, cbb, cbc,
cca, ccb, ccc}
its also asking in part b:
For each integer n >= 0, let S_n = the number of strings of a's, b'c, and c's of length n that do not contain the pattern aa. Find S_O, S_1, S_2, and S_3
So would S_O = 1; S_1 = 3; S_2 = 5 or would string of length 2, that do not contain aa be more?
length 2: {a,b}, {a,c}, {b,c}, {b,b}, {c,c}
like: length 2: ab,ba,ac,ca,bc,cb,bb,cc
so S_2 = 8
and is S_3 = 22?
for part c its asking:
find a recurrence rleation for s_0, S_1, S_2...
and the answer is: [tex]s_{k} = 2*s_{k-1} + 2*s_{k-2}[/tex]
and for part D:
they are saying to use part b and c to find the number of strings of a's , b's, and c's of length four that do not contian the pattern aa.
But I thought I just foudn this in part a and b didn't i?
Thanks!
Consdier the set of all strings of a's, b's, and c's.
a. make a list of all of these strings of lengths zero, one, two, and three that do not contain the pattern aa.
Okay so i have the following:
note e: stands for empty
length 0: e
length 1: a; b; c;
length 2: {a,b}, {a,c}, {b,c}, {b,b}, {c,c}
okay for length 2, I'm confused, do they want all possibe like for instance:
is {a,b} equal to {b,a}? like {1,2} would be equal to {2,1} if we are just talking about sets, order doesn't matter but I'm not sure if they are talking about sets or not...
Length 3: {aba, abb, abc, aca, acb, acc, bab, bac,
bba, bbb, bbc, bca, bcb, bcc, bcab, cac, cba, cbb, cbc,
cca, ccb, ccc}
its also asking in part b:
For each integer n >= 0, let S_n = the number of strings of a's, b'c, and c's of length n that do not contain the pattern aa. Find S_O, S_1, S_2, and S_3
So would S_O = 1; S_1 = 3; S_2 = 5 or would string of length 2, that do not contain aa be more?
length 2: {a,b}, {a,c}, {b,c}, {b,b}, {c,c}
like: length 2: ab,ba,ac,ca,bc,cb,bb,cc
so S_2 = 8
and is S_3 = 22?
for part c its asking:
find a recurrence rleation for s_0, S_1, S_2...
and the answer is: [tex]s_{k} = 2*s_{k-1} + 2*s_{k-2}[/tex]
and for part D:
they are saying to use part b and c to find the number of strings of a's , b's, and c's of length four that do not contian the pattern aa.
But I thought I just foudn this in part a and b didn't i?
Thanks!
Last edited: