CPTR
324 Spring 2006 Exam 1 Name ________________________

** Multiple Choice**: Select the

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 *L _{1}
*Í

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 ´ S_{e} ® Q

- Let
*S**= {a, b}*. Draw the transition diagram for athat accepts the set of all strings that have__DFA__*aba*as a substring. (8 points)

- Let
*S**= {a, b}*. Draw the transition diagram for anthat accepts the__NFA__of the following two languages: (8 points)__union__

L_{1} = {all strings
that begin with two consecutive *a*’s}

L_{2} = {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. L_{1} = {*w**Î**S** ^{*}* |

b. L_{2} = {*w**Î**S** ^{*}* | every odd position is an

c. L_{3} = {*w**Î**S** ^{*}* |

9. ** Using the construction to convert a Regular
Expression to an NFA**, draw an NFA that accepts

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, q_{0}, F) be an
NFA. Construct equivalent DFA M = (Q’, S, d’, q_{0}’, F’) where

Q’ =
_______________________________________,

d’(R,a) = {qÎQ | qÎ d(r,a) for some rÎR}, for all RÎQ’ and aÎ S,

q_{0}’ =
_______________________________________, 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 *q _{rip}* is removed from the

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

i.
Let *q _{rip}* be state 3. What would the label of the transition from
state 1 to state 2 become? (4 points)

ii. Let q_{rip} 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, q _{0},
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 = {ww^{R }| w Î S* and w^{R} is the reverse of w}