CPTR 324 Spring 2006 Exam 1 Name ________________________

 

Multiple Choice: Select the best answer for each of the following: (2 points each)

1.      An alphabet is

a.       a possibly infinite set of letters

b.      a finite set of letters

c.       a possibly infinite set of symbols

d.      a finite set of symbols

 

2.      A string is

a.       a finite sequence of symbols

b.      a finite set of symbols

c.       a possibly infinite sequence of symbols

d.      a possibly infinite set of symbols

 

3.      A language is

a.       a possibly infinite set of strings

b.      a finite set of strings

c.       a possibly infinite sequence of strings

d.      a finite sequence of strings

 

4.      A regular language is

a.       a language that is accepted by a DFA

b.      a language that is accepted by an NFA

c.       a language that can be represented by a regular expression

d.      all of the above

 

5.      True or False: Indicate if each statement is true (meaning always true) or false: (2 points each)

T or F Every regular language contains the empty string e.

 

T or F Every finite language is regular.

 

T or F Every infinite language is regular.

 

T or F The class of regular languages is closed under union.

 

T or F If a language is not regular then its complement is not regular.

 

T or F If L1 L2 and L2 is regular, then L1 is regular.

 

T or F There exist languages that are accepted by NFAs for which no equivalent DFA exists.

 

T or F The transition function for a DFA is d: Q S S

 

T or F The transition function for a NFA is d: Q Se Q


  1. Let S = {a, b}. Draw the transition diagram for a DFA that accepts the set of all strings that have aba as a substring. (8 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  1. Let S = {a, b}. Draw the transition diagram for an NFA that accepts the union of the following two languages: (8 points)

 

L1 = {all strings that begin with two consecutive as}

L2 = {all strings that contain the substring bab}


8.      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* | w contains at least 3 symbols and the second symbol is b}

 

 

 

 

 

 

 

 

 

 

 

 

 

b.      L2 = {wS* | every odd position is an a}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

c.       L3 = {wS* | w does not end with bb}

 

 

 

 

 

 

 


9.      Using the construction to convert a Regular Expression to an NFA, draw an NFA that accepts a(bb)*. (6 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

10.  The Subset Construction was used to prove that for every NFA there is exists an equivalent DFA, i.e., a DFA that accepts the same language. Complete the details of the construction below by filling in the blanks. (6 points)

 

Subset construction

 

Let N = (Q, S, d, q0, F) be an NFA. Construct equivalent DFA M = (Q, S, d, q0, F) where

 

Q = _______________________________________,

d(R,a) = {qQ | q d(r,a) for some rR}, for all RQ and a S,

 

q0 = _______________________________________, and

 

F = _______________________________________

 

 


11.  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 GNFAs with start state s and accept state a.

 

 

i.         Let qrip be state 3. What would the label of the transition from state 1 to state 2 become? (4 points)

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

 

 

 

 


12.  Using the Minimization Algorithm made possible by the Myhill-Nerode Theorem, draw the smallest DFA equivalent to the one below. The steps of the algorithm are given for reference: (NOTE: All states in this machine ARE reachable.) (8 points)

 

Minimization Algorithm for DFA M = (Q, S, d, q0, F):

 

1.        Remove all unreachable states.

2.        Partition the state set of M into Q-F | F.

3.        For each partition, for every pair of states p and q in the partition, for some alphabet symbol a, consider d(p,a) and d(q,a). If d(p,a) and d(q,a) are in separate partitions, then place p and q in separate partitions.

4.        Repeat step 2 until no further partitioning occurs on any alphabet symbol.

 

Recall that to draw the resulting transition diagram, each partition becomes a state.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


13.  Let S = {0, 1}. Use the Pumping Lemma to show that the following language is not regular. (10 points)

 

A = {wwR | w S* and wR is the reverse of w}