Copyright © 2006 Gradiance Corporation.

 

 

     

Regular Expressions

 

 

 

Regular expressions and conversions with finite automata.

 

1.  

Apply the McNaughton-Yamada-Thompson construction in Section 3.7.4 (p. 159) to convert the regular expression (0+1)*(0+ε) to an epsilon-NFA. Count

  1. The number of states.
  2. The number of states that have more than one out-arc.
  3. The number of states that have more than one in-arc.
  4. The number of arcs labeled ε

Then, identify the true statement about your epsilon-NFA from the list below:

 

 

 

 a) 

There are 7 states.

 

 b) 

There are 16 states.

 

 c) 

There are 3 states with more than one arc out.

 

 d) 

There are 14 states.

 

 

 

 

 

2.  

The UNIX-style regular expression [a-e]*f?bc* generates which of the following strings?

 

 

 

 a) 

acfbfc

 

 b) 

ccbfbabc

 

 c) 

abb

 

 d) 

edcffb

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.  

Suppose that in some language a real number is represented by the following elements, which must be in order, if they occur at all (i.e., are not optional):

  1. An optional minus sign (-).
  2. One or more digits (0 through 9).
  3. A decimal point.
  4. Zero or more digits.
  5. An optional exponent, consisting of:
    • An "E" in upper or lower case.
    • An optional minus sign.
    • One or more digits.

Write a regular expression for real numbers in the form described above. There are several options, of course. Identify from the list below, one of the possible regular expressions that denotes all these real numbers and nothing else.

 

 

 

 a) 

-?[0-9]+.[0-9]*[Ee]-?[0-9]+

 

 b) 

-?[0-9][0-9]*.[0-9]*((E|e)-[0-9][0-9]*)?

 

 c) 

-?[0-9]+.[0-9]*([Ee]-?[0-9]+)?

 

 d) 

-?[0-9]*.[0-9]*([Ee]-?[0-9]+)?

 

 

 

 

 

4.  

Identify from the list below the regular expression that generates all and only the strings over alphabet {0,1} that end in 1.

 

 

 

 a) 

1*0*1

 

 b) 

(0+1+)*1

 

 c) 

(0*1*)+1

 

 d) 

(0+1)*10*