Regular Expressions

Regular expressions are useful for representing certain sets of strings in an algebraic fashion. Regular expressions (RE) describe the languages accepted by finite state automata. 

1) If a letter a belongs to Ʃ, then it is a RE.

2) If R1 and R2 are two RE then, (R1+R2) is also a RE. + operates as a OR operation.

3) The concatenation of two regular expressions R1 and R2, written as R1. R2, is also a regular expression.  

4) R1* is the Kleene’s closure of R1. Kleene’s closure of R1 is 0 or more occurrences of R1. The Kleene’s closure of a RE is also a RE.

5) R1⁺ is the positive closure of R1 which is also a RE. Positive closure of R1 is 1 or more occurrences of R1.

For example

1) Write a RE for any number of 0’s followed by any number of 1’s followed by any number of 1’s.

Ʃ = {0, 1, 2}

RE = 0* . 1* . 2*

 This means that 0 or more number of zeroes followed by 0 or more number of ones followed by 0 or more number of two’s can occur.

2) Write a RE such that string ‘101’ must be present in a binary string.

Ʃ ={0, 1}

This means that the RE should be of the form

 (anything) .101. (anything)

therefore the RE will be

RE= (0+1)*. 101. (0+1)*

(0+1)* is any number of 0’s or 1’s

3) Write a RE for all strings that end in 101

Ʃ= {0, 1}

RE = (0+1)*. 101

This means that any number of 0’s or 1,s can come before string 101, and after 101 nothing must come.

4) Write a RE to check if a given number is a decimal number

Let us define a = + (positive sign),

                      b = -  (negative sign) and

                      d = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

RE = (a + b + ^) . d⁺ . ( . d⁺ + ^)

Here at first we can get a positive sign or a negative sign or nothing (^). That should be followed by atleast 1 decimal, therefore we have used the positive closure (⁺). That can be followed by a decimal point and if there is decimal point, it has to be followed by atleast 1 decimal. If it doesn’t get a decimal point then it has to be followed by nothing (^).

5) Write a RE for accepting all strings with even length.

Ʃ = {0, 1}

RE = ((0+1) . (0+1))*

For strings with even length the least number of times numbers can appear is 2. Therefore there has to be 0 or 1 followed by a 0 or 1 and this can appear any number of times.

6) Write a RE with accepts strings that do not have substring 00 and ends in 1.

Ʃ = {0, 1}

RE= (1+01)⁺

Here either a 1 can occur, but if a 0 occurs it has to be followed by a 1, so that substring 00 will be rejected and this can occur one or more number of times.

7) Write a RE for accepting strings with odd number of 1’s.

Ʃ = {0, 1}

RE = 0*. 1. 0*. (1. 0*. 1. 0*)*

Here for odd number of 1’s the least number of times 1 can occur is 1, so we can have any number of 0’s followed by 1 followed by any number of 0’s. Next if we come across any other 1, it has to be followed by another 1 to make the number of 1’s odd. So if we get another 1, it can be followed by any number of 0’s and again followed by a 1 and then can be followed by any number of 0’s and this can occur any number of times.

8) Write a RE for accepting a string with even number of 0’s followed by odd number of 1’s.

Ʃ = {0, 1}

RE= (0. 0)*.1.  (1. 1)*

Here for even number of 0’s 0 should occur in a pair and that can be repeated any number of times. That has to be followed by odd number of 1’s. Again least number of times it can occur is 1 and if another 1 occurs, it has to followed by the another 1.

Feel free to comment below, if you still have some doubts.