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’ ).
- (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’ ).
- (7 pts.) Consider the recursively defined language, L2:
- i) x Î L2 and y Î L2
- ii) if w Î L2, then so is wxw Î L2
Find all strings in L2with length less than 7 characters (note: ‘w’ is a meta symbol).
- (7 pts.) Consider the recursively defined language, L3:
- i) acÎ L3 and gbb Î L3
- ii) if w Î L3, then so is gwa Î L3
Find all strings in L3 with length less than 9 characters (note: ‘w’ is a meta symbol).
- (7 pts.) Given the alphabet {xyz abc}, give a recursive definition for the language whose words do notcontain the string xyzxyz.
Notes:
- Treat ‘xyz’ and ‘abc’ as single letters (i.e. atomic tokens that cannot be decomposed).
- 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+,w2. 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.
- (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.
- (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.
- yyxxxy,
- xyyyxxyy,
- xyyxyyxxxyy,
- yyxyyxxyxy,
- yyxyyxxyyy
- (5 pts.) Consider the language S*, where S = {p q}
- How many words does this language have of length 2? List them.
- How many words does this language have of length 3? List them.
- How many of length 4? (Don’t list them.)
- How many of length n?
- (6 pts.) Consider the language S*, where S = {e f g h}
- How many words does this language have of length 2? List them.
- How many words does this language have of length 3? List them.
- How many of length 4? (Don’t list them.)
- How many of length n?
- (5 pts.) Consider the language S* where S = {yy xxyxx yxxyxxyxxy}
- Is yxxyxxyxxyxxy in S*? Why or Why not?
- Is xxyxxyyxxyxxin S*? Why or Why not?
- What is the most specific, but general, comment that can be made about this language?
- (5 pts.) Consider the language S*, where S = {pq qp p}
- List all of the words with less than five letters.
- Is pqqqp a word in this language?
- Give an English description of the words in this language (note, there is a pattern).
- (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.
- (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.)
- (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)
- (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.
- (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