Prentice-Hall     Addision-Wesley

Copyright © 2007 Gradiance Corporation.

 

Gradiance Online Accelerated Learning

 

 

 

 

 

     

Regular Expressions --- Algebra and FA Equivalence

 

 

1.  

When we convert an automaton to a regular expression, we need to build expressions for the labels along paths from one state to another state that do not go through certain other states. Below is a nondeterministic finite automaton with three states. For each of the six orders of the three states, find regular expressions that give the set of labels along all paths from the first state to the second state that never go through the third state.

http://www.gradiance.com/phmu/pictures/ullman_nfa3.gif

Then identify one of these expressions from the list of choices below.

 

 

 

 a) 

10* represents the paths from C to A that do not go through B.

 

 b) 

0+ represents the paths from B to A that do not go through C.

 

 c) 

0(10)* represents the paths from B to A that do not go through C.

 

 d) 

1(0+1010)* represents the paths from C to A that do not go through B.

 

 

 

 

 

2.  

Apply the construction in Figure 3.16 (p. 104) and Figure 3.17 (p. 105) to convert the regular expression (0+1)*(0+ε) to an epsilon-NFA. Then, identify the true statement about your epsilon-NFA from the list below:

 

 

 

 a) 

There are 10 states.

 

 b) 

There are 14 states.

 

 c) 

There are 12 states with more than one arc in.

 

 d) 

There are 16 states.

 

 

 

 

 

3.  

In this question you are asked to consider the truth or falsehood of six equivalences for regular expressions. If the equivalence is true, you must also identify the law from which it follows. In each case the statement R = S is conventional shorthand for "L(R) = L(S)." The six proposed equivalences are:

  1. 0*1* = 1*0*
  2. 01φ = φ
  3. ε01 = 01
  4. (0* + 1*)0 = 0*0 + 1*0
  5. (0*1)0* = 0*(10*)
  6. 01+01 = 01

Identify the correct statement from the list below.

Note: we use φ for the empty set, because the correct symbol is not recognized by Internet Explorer.

 

 

 

 a) 

01+01 = 01 is false.

 

 b) 

(0* + 1*)0 = 0*0 + 1*0 follows from the distributive law of concatenation over union.

 

 c) 

(0* + 1*)0 = 0*0 + 1*0 follows from the associative law for concatenation.

 

 d) 

(0*1)0* = 0*(10*) follows from the idempotent law for union.

 

 

 

 

 

4.  

Converting a DFA such as the following:

http://www.gradiance.com/phmu/pictures/gradiance_dfa111605.gif

to a regular expression requires us to develop regular expressions for limited sets of paths --- those that take the automaton from one particular state to another particular state, without passing through some set of states. For the automaton above, determine the languages for the following limitations:

  1. LAA = the set of path labels that go from A to A without passing through C or D.
  2. LAB = the set of path labels that go from A to B without passing through C or D.
  3. LBA = the set of path labels that go from B to A without passing through C or D.
  4. LBB = the set of path labels that go from B to B without passing through C or D.

Then, identify a correct regular expression from the list below. Note: there are several different regular expressions possible for each of these languages. However, each of the correct answers can be thought of as built from more limited components. For example, the regular expression 1 is the set of path labels that go from A to B without passing through any of the four states.

 

 

 

 a) 

LBB = (00*1)*

 

 b) 

LBA = 0(00*10)*

 

 c) 

LAB = 0*1(01+10)*

 

 d) 

LBB = (0(00*10)*)*

 

 

 

 

 

5.  

Consider the following identities for regular expressions; some are false and some are true. You are asked to decide which and in case it is false to provide the correct counterexample.

(a) R(S+T)=RS+RT
(b) (R*)*=R*
(c) (R*S*)*=(R+S)*
(d) (R+S)*=R*+S*
(e) S(RS+S)*R=RR*S(RR*S)*
(f) (RS+R)*R=R(SR+R)*

 

 

 

 a) 

(d) is true

 

 b) 

(e) is true

 

 c) 

(d) is false and a counterexample is:
R={a,ε},T={b}, S={a,ε}

 

 d) 

(e) is false and a counterexample is:
R={a},T={a}, S={b}