- #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: