Question

Problem 5 Regular Expressions.

a) Define a regular expression for all strings of odd length, over the alphabet of {0}.

b) Define a regular expression for identifiers over the alphabet of {A,B,C,a,b,c,0,1,2,3,4,5,6,7,8,9}, such

that an identifier must begin with an alphabetic character and must contain at least one numeric character.

c) Try to modify the definition above so that identifiers still begin with an alphabetic character, but after

that, it must contain at least one numeric, at least one lower-case letter, and at least one upper-case letter,

but no restrictions on where they can/must occur.

Answer 1

Answer for (a):

The regular expression for all strings of odd length, over the alphabet of {0} is:  (00)^*0

Answer for (b):

The regular expression for identifiers over the alphabet of {A,B,C,a,b,c,0,1,2,3,4,5,6,7,8,9}, such that an identifier must begin with an alphabetic character and must contain at least one numeric character is :

(A+B+C+a+b+c) (A+B+C+a+b+c)^* (0+1+2+3+4+5+6+7+8+9)

(A+B+C+a+b+c+0++1+2+3+4+5+6+7+8+9)^*

Answer for (C):

X -> A+B+C+a+b+c

N -> 0+1+2+3+4+5+6+7+8+9

Y -> A+B+C

Z -> a+b+c

The regular expression is : X(N+Y+Z) (X+N)^* (N+Y+Z) (X+N)^* (Y+N+Z) (X+N)^*