Posted: January 18th, 2016

(4 pts.) Given a universe U with subsets, A, B, and C. Draw a shaded Venn Diagram that represents the following sets: ( B Ç A ) È ( C Ç A’ ).

1. (4 pts.) Given a universe U with subsets, A, B, and C. Draw a shaded Venn Diagram that represents the following sets: ( B Ç A ) È ( C Ç A’ ).

 

 

 

 

2. (7 pts.) Consider the recursively defined language, L₂:
3. i) x Î L₂ and y Î L₂
4. ii) if w Î L₂, then so is wxw Î L₂

 

Find all strings in L₂with length less than 7 characters (note: ‘w’ is a meta symbol).

 

3. (7 pts.) Consider the recursively defined language, L₃:
4. i) acÎ L₃ and gbb Î L₃
5. ii) if w Î L₃, then so is gwa Î L₃

 

Find all strings in L₃ with length less than 9 characters (note: ‘w’ is a meta symbol).

 

4. (7 pts.) Given the alphabet {xyz abc}, give a recursive definition for the language whose words do notcontain the string xyzxyz.

 

Notes:

1. Treat ‘xyz’ and ‘abc’ as single letters (i.e. atomic tokens that cannot be decomposed).

 

2. This must be a constructive definition (i.e. in the definition, you cannot say what is not in the language. That is, the definition cannot use constructs like: ‘not,’Ø, ≠, +. Also you cannot use exponents in the meta variable: w⁺,w². You can use repeated variables, ww or multiple variables w, x. These same constraints apply to all of the remaining recursive questions. Basically, they should look similar to Questions 2 and 3 above.

 

5. (7 pts.) Given the alphabet {xyz abc}, give a recursive definition for the language whose words contain the string xyzxyz  (note: there are an infinite number of words in this language, same constraints as in Question 4.

 

6. (10 pts.) Let L = {x yy  xxy}

Which of the following strings are in L*, which are not? Show why you answered yes or no.

1. yyxxxy,
2. xyyyxxyy,
3. xyyxyyxxxyy,
4. yyxyyxxyxy,
5. yyxyyxxyyy

 

7. (5 pts.) Consider the language S*, where S = {p q}

 

1. How many words does this language have of length 2? List them.
2. How many words does this language have of length 3? List them.
3. How many of length 4? (Don’t list them.)
4. How many of length n?

 

8. (6 pts.) Consider the language S*, where S = {e f  g h}
9. How many words does this language have of length 2? List them.
10. How many words does this language have of length 3? List them.
11. How many of length 4? (Don’t list them.)
12. How many of length n?

 

9. (5 pts.) Consider the language S* where S = {yy  xxyxx  yxxyxxyxxy}
10. Is yxxyxxyxxyxxy in S*? Why or Why not?
11. Is xxyxxyyxxyxxin S*? Why or Why not?
12. What is the most specific, but general, comment that can be made about this language?

 

10. (5 pts.) Consider the language S*, where S = {pq qp p}
11. List all of the words with less than five letters.
12. Is pqqqp a word in this language?
13. Give an English description of the words in this language (note, there is a pattern).

 

11. (5 pts.) Show that the following is another recursive definition of the set ODD

(keep in mind you’ll need say something about even numbers too):

Rule 1:   1 and 3 are in ODD.

Rule 2:   If x is in ODD, then so is x + 4.

 

12. (10 pts.) Given the alphabet {ggg mmm}, give a recursive definition for the language that

only contains odd length strings. (Constructive definitions only, see Question 4.)

 

13. (10 pts.) Give a recursive definition for the set of strings of letters

    a, b, c, d, e, f, g, h

    (and only these 8 letters) that cannot end with the letter ‘a’.

    (Constructive definitions only, see Question 4)

 

14. (7 pts.) Given an alphabet L that consists of the letters of your last name, give all strings in

L* with length less than 4.

 

15. (5 pts.) Given an alphabet L that consists of the letters of you first name, give a recursive

definition in which all strings of length greater than 1 begin with the third letter in your