Prentice-Hall     Addision-Wesley

Copyright © 2007 Gradiance Corporation.

 

Gradiance Online Accelerated Learning

 

 

 

 

 

     

Regular Expressions --- Basics

 

 

1.  

Consider the languages:

(a) {02n1n | n > 0}
(b) {05n1n | n > 0}
(c) {w | w a string of 0's and 1's such that when interpreted in reverse as a binary integer it is a multiple of 5}
(d) {0n1n|n>0}
(e) {w | w a string of 0's and 1's such that its length is a perfect square}
(f) {w | w string of 0's and 1's such that when interpreted as a binary integer it is not a multiple of 5}
(g) {w | w a string of 0's and 1's such that its length is not a perfect cube}
(h) {w | w a string of 0's and 1's such that the number of 0's is not equal to twice the number of 1's}

Which is a regular language?

 

 

 

 a) 

(f)

 

 b) 

(d)

 

 c) 

(e)

 

 d) 

(a)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.  

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

 

 

 

 a) 

(0*+1)*

 

 b) 

(0+1)*1+

 

 c) 

0+(0+1)*1

 

 d) 

(0+1)*10*

 

 

 

 

 

3.  

Here are seven regular expressions:

  1. (0*+10*)*
  2. (0+10)*
  3. (0*+10)*
  4. (0*+1*)*
  5. (0+1)*
  6. (0+1*0)*
  7. (0+1*)*

Determine the language of each of these expressions. Then, find in the list below a pair of equivalent expressions.

 

 

 

 a) 

(0*+10)* and (0+1*)*

 

 b) 

(0*+10*)* and (0*+1*)*

 

 c) 

(0+10)* and (0*+1*)*

 

 d) 

(0+1*0)* and (0*+1*)*

 

 

 

 

 

4.  

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) 

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

 

 b) 

(0*1)0* = 0*(10*) is false.

 

 c) 

01φ = φ is false.

 

 d) 

0*1* = 1*0* follows from the commutative law of concatenation.

 

 

 

 

 

5.  

Which of the following strings is NOT in the Kleene closure of the language {011, 10, 110}?

 

 

 

 a) 

011011110

 

 b) 

10011101

 

 c) 

11001110

 

 d) 

11010110

 

 

 

 

 

6.  

Which among the following languages is not regular (cannot be defined by a regular expression or finite automaton)?

 

 

 

 a) 

L={x | x=camcbn, n, m positive integers}

 

 b) 

L={x | x=anbn, n a positive integer}

 

 c) 

L={x | x=am(bc6)n, n, m positive integers}

 

 d) 

L={x | x=ambn, n, m positive integers}

 

 

 

 

 

7.  

Here is a finite automaton:

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

Which of the following regular expressions defines the same language as the finite automaton? Hint: each of the correct choices uses component expressions. Some of these components are:

  1. The ways to get from A to D without going through D.
  2. The ways to get from D to itself, without going through D.
  3. The ways to get from A to itself, without going through A.

It helps to write down these expressions first, and then look for an expression that defines all the paths from A to D.

 

 

 

 a) 

(01+10)(0(01+10))*(11)*

 

 b) 

(01+10)(11+(01+10)0)*

 

 c) 

(01+10)(11*+0(01+10))*

 

 d) 

((01+10)(11)*0)*(01+10)(11)*