CPTR 324 Spring 2003 Exam 1 Name ________________________

1. Definitions: Define the following terms (3 points each)

a. alphabet

b. string

c. language

2. Matching: Choose the notation that correctly defines each of the following: (3 points each)

_____ transition function for a DFA

_____ transition function for an NFA

_____ union of two languages A and B

_____ concatenation of two languages A and B

_____ star of a language A

a. d: Q ´ S ® S

b. d: Q ´ S ® Q

c. d: Q ´ S ® 2^Q

d. d: Q ´ S_e ® S_e

e. d: Q ´ S_e ® Q

f. d: Q ´ S_e ® 2^Q

g. {w | w Î A or w Î B}

h. {w | w Î A and w Î B}

i. {xy | x Î A or y Î B}

j. {xy | x Î A and y Î B}

k. {w | w Ï A}

l. {w₁w₂…w_n | n > 0 and each w_i Î A }

m. {w₁w₂…w_n | n ≥ 0 and each w_i Î A}

3. Let S = {a, b}. Give regular expressions for the following languages. (For full credit, keep them as simple as possible.) (5 points each)

a. L₁ = {wÎS^* | the length of w is a multiple of 3}

b. L₂ = {wÎS^* | every a, if there is one, is followed immediately by a b}

c. L₃ = {wÎS^* | w does not begin with aa}

4. Let S = {a, b}. Draw the transition diagram for a DFA that accepts the language a(ab)*b. (8 points)

5. Let S = {a, b}. Show that the language of all strings in S* that do not have 3 a’s in a row is regular. (8 points)

6. The procedure CONVERT(G) takes a GNFA G and returns a regular expression that denotes L(G).

a. In the procedure, when q_rip is removed from the GNFA, the transition label between q_i and q_j is replaced by what regular expression (refer to diagram below)? (5 points)

b. Consider the following GNFA with start state s and accept state a.

i. Let q_rip be state 3. What would the label of the transition from state s to state a become? (5 points)

ii. Let q_rip be state 3. What would the label of the transition from state 2 to state 2 become? (5 points)

7. Using the construction to convert a Regular Expression to an NFA, draw an NFA that accepts (ab)*. (5 points)

8. The Cross-product construction was used to prove that the class of regular languages is closed under union, intersection, and set difference. The construction was the same except for the designation of F, the set of final states. Give the formal notation for the set of final states for each of the following: (The construction is given below as a reference.) (6 points)

a. Union

F = _______________________________

b. Intersection

F = _______________________________

c. Set difference

F = _______________________________

Cross-product construction

Let M₁ = (Q₁, S, d₁, q₁, F₁) and M₂ = (Q₂, S, d₂, q₂, F₂).

Construct M = (Q, S, d, q₀, F) where

Q = Q₁ ´ Q₂ = {(r₁, r₂) | r₁ Î Q₁ and r₂ Î Q₂},

d((r₁, r₂), a) = (d(r₁, a), d(r₂, a)) for each (r₁, r₂) Î Q and each a Î S,

q₀ = (q₁, q₂), and

F = ….

9. Let S = {a, b}. Using the equivalence relation R_L (given below for reference) defined in the Myhill-Nerode Theorem, show that any DFA accepting L = {wÎS^* | w contains an even number of a's and exactly one b} has at least 5 states. (10 points)

The equivalence relation R_L is defined for any language L as follows:

x R_L y if and only if for all z Î S^*

xz Î L Û yz Î L

10. Let S = {a, b}. Use the Pumping Lemma to show that the following language is not regular. (9 points)

A = {aⁱb^j | i £ j}