Practice Questions on Regular Expressions
Instructor: Asma Sanam Larik
1. Write a regular expression for each of the following sets of binary strings.
Use only the basic operations.
a.
b. all binary strings except empty string _______________________
c. begins with 1 and ends with a 1 ____________________________
d. ends with 00 ___________________________________________
e. contains at least three 1s _________________________________
2. Write a regular expression to describe inputs over the alphabet {a, b, c}
a. that are in sorted order _________________________________
b. containing at least one a and at least one b__________________
3. Write a regular expression for each of the following sets of binary strings.
Use only the basic operations.
a.
b. contains the substring 110 _____________________________
c. doesn't contain the substring 110 ________________________
d. whose tenth symbol from the right is 1_____________________
e. not containing 101 as a substring
2. Write a regular expression for each of the following sets of binary strings.
Use only the basic operations.
a.
b. number of 0s is a multiple of 3 _____________________________
c. has at least 3 characters, and the third character is 0 ___________
d. starts and ends with the same character _____________________
e. length is at least 1 and at most 3 ___________________________
2. Write a Regular Expression for the following language
a. L= { an bm | n>=4, m<=3}
b. L= { an bm | (n +m) is even }
Practice Questions on Regular Expressions
c. L={w Є {0,1}* | w has at least one pair of consecutive zeros}
d. L={w Є {0,1}* | w has no pair of consecutive zeros}
3. What is the language denoted by the following RE
a. R= (a+b)*(a+bb)
__________________________________________________
b. R= (aa)* (bb)*b
__________________________________________________
Answers:
1) 2)
a. (0+1)(0+1)* a. a*b*c*
b. 1(0+1)*1 b. (a+b+c)*a(a+b+c)*b(a+b+c)* +
c. (0+1)*00 (a+b+c)* b(a+b+c)*a(a+b+c)*
d.
(0+1)*1(0+1)*1(0+1)*1(0+1)*
3) 4)
a. (0+1)*110(0+1)* a. (0+1)(0+1)0(0+1)*
b. (0+10)*1* b. 1* + (1*01*01*01*)+
c. (0+1)*1(0+1)9 c. 1(0+1)*1 + 0(0+1)*0 +0 + 1
d. (0*1*00)* 0*1*
d. (0+1) + (0+1)(0+1) + (0+1)(0+1)(0+1)
5) 6)
4 4 4 2 4 3
a. a a*+ a a*b + a a*b + a a*b = a. set of strings terminated by a or bb
a4 a*(Є+b+b2 + b3 ) b. even number of a’s followed by odd
b. (aa)* (bb)* + (aa)* a (bb)* b number of b’s
c. (0+1)* 00 (0+1)*
d. (1* 011*)*0+ 1*0
