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 2Q

d.      d: Q Se Se

e.       d: Q Se Q

f.        d: Q Se 2Q

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.         {w1w2wn | n > 0 and each wi A }

m.     {w1w2wn | n ≥ 0 and each wi 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.       L1 = {wS* | the length of w is a multiple of 3}

 

 

 

 

 

 

 

 

 

 

 

 

 

b.      L2 = {wS* | every a, if there is one, is followed immediately by a b}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

c.       L3 = {wS* | w does not begin with aa}

 

 

 

 

 

 

 


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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  1. Let S = {a, b}. Show that the language of all strings in S* that do not have 3 as 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 qrip is removed from the GNFA, the transition label between qi and qj 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 qrip be state 3. What would the label of the transition from state s to state a become? (5 points)

 

 

 

 

 

 

 

ii.       Let qrip 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 M1 = (Q1, S, d1, q1, F1) and M2 = (Q2, S, d2, q2, F2).

 

Construct M = (Q, S, d, q0, F) where

 

Q = Q1 Q2 = {(r1, r2) | r1 Q1 and r2 Q2},

 

d((r1, r2), a) = (d(r1, a), d(r2, a)) for each (r1, r2) Q and each a S,

 

q0 = (q1, q2), and

 

F = .

 

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

 

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

x RL 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 = {aibj | i j}