The following are the copies of the problems 4. Let X = {aa, bb} and Y = {?, b,

Question

The following are the copies of the problems

4. Let X = {aa, bb} and Y = {?, b, ab}.?

a) List the strings in the set XY. ?

b) How many strings of length 6 are there in X* ??

c) List the strings in the set Y* of length three or less.

d) List the strings in the set X*Y* of length four or less.

5. Let L be the set of strings over {a, b} generated by the recursive definition?

iii) Closure: a string v is in L only if it can be obtained from the basis by a finite number of iterations of the recursive step.

a) List the elements in the set L0, L1, and L2.?

b) Is the string bbaaba in L? If so, trace how it is produced. If not, explain why not.

c) Is the string bbaaaabb in L? If so, trace how it is produced. If not, explain why not.

6. Give a recursive definition of the set of strings over {a, b} that contain at least one b and have even number of a’s before the first

b. For example, bab, aab, and aaaabababab are in the set, while aa, abb are not.

Explanation / Answer

4a) Strings in set XY are {aa, aab, aaab, bb, bbb, bbab}

b) Strings of length 6 in X* are {aaaaaa, bbbbbb, aaaabb, aabbaa, bbaaaa, aabbbb, bbbbaa, bbaabb}

c) Strings of length 3 or less in Y* are {, b, ab, bb, bab, abb, bbb}

d) Strings of length 4 or less in X*Y* can be computed in the follwing way: X* elements of legth 4 or less = {, aa, bb, aaaa, aabb, bbaa, bbbb} Y* elements of legth 4 or less= {, b, ab, bb, bab, abb, bbb, abab, babb, bbab, abbb, bbbb} Therefore elements of X*Y* of length four or less are: {, b, ab, bb, bab, abb, bbb, abab, babb, bbab, abbb, bbbb, aa, aabaaab, aabb, aaaa, aabb, bbaa}

---------------------------x-------------------------------

-5a) Assume that L0 denotes the set of all of the strings in the language L that are generated with zero applications of the recursive step (i.e., the basis), and Li denotes the set of all of the strings in the language L that are generated with exactly i applications of the recursive step, for i 0.

L0 = {b}

L1 = {bb, bab, bba}

L2 = {bbb, babb, bbab, bbab, babab, bbaab, bbba, babba, bbaba, bbba, bbaba, bbbaa}

b) The string bbaaba does not belong to L.

Explanation: If bbaaba were in L, the only two possible ways to have generated it would be:

1. If the string u1 = bbaa were in L, because if it were, then applying the recursive step u1ba will produce the string we want. But u1 = bbaa is not in L, because the only way to construct u1 using the recursive step would be if u2 = ba were in L. But u2 = ba is not in L, because the only way to construct u2 using the recursive step would be if u3 = were in L, but it is not.

2. If the string u1 = baab were in L, because if it were, then applying the recursive step bu1a will produce the string we want. But u1 = baab is not in L, because if it were then EITHER baa would belong in L (but it can’t because the recursive step would only construct it if ba were in L but it is not because in not in L); OR ba would belong in L, but we should showed it is not.

c) The string bbaaaabb does not belong to L.

Explanation: Given the fact that w = bbaaaabb ends with two bs, then the only way in which w could have been generated is using the recursive step u1b where u1 = bbaaaab belongs to L. Now, let’s see if u1 belongs to L. If it did, it must have been generated by either using the recursive step ub or the recursive step uab.

• Hypothesis 1. u1 = bbaaaab was generated using the recursive step u2b where u2 = bbaaaa belongs to L. Given the fact that u2 ends on aa, then the only way it could have been generated is using the recursive step bu3a where u3 = baaa belongs to L. Similarly, u3 must have been generated from aa. But, aa does not belong to L, as each string in L contains at least one b (see basis). So hypothesis 1 fails.

• Hypothesis 2. u1 = bbaaaab was generated using the recursive step u4ab where u4 = bbaaa belongs to L. Given the fact that u4 ends on aa, then the only way it could have been generated is using the recursive step bu5a where u5 = baa belongs to L. Similarly, u5 must have been generated from a. But, a does not belong to L, as each string in L contains at least one b (see basis). So hypothesis 2 fails.

Hence, w = bbaaaabb cannot belong to L since it cannot have been constructed from the basis using recursive steps.

------------------------------x-----------------------------

6 Let L be the set of strings over = a, b which contain twice as many a’s as b’s, the language L can be defined recursively as follows:

• Basis: L. • Recursive Step: if u L and u can be written as u = xyz, where x, y, z, , thus: 1. xayazb L, 2. xaybza L, and 3. xbyaza L

• Closure: A string u is L only if string u can be generated from using a finite number of recursive steps.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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