Regular Expression Examples

For Complete YouTube Video: Click Here

In this class, We discuss Regular Expression Examples.

The reader should have prior knowledge of regular expression to finite automata. Click Here.

Write regular expressions for the following language over the alphabet Σ = {0,1}.

Example 1: The set of all strings begin with 110.

We write the regular expression for 110 using the concatenation operator.

One followed by one followed by zero.

Whenever we have a string followed by some other string, we use concatenation.

The regular expression to accept 110 is 1.1.0 or 110.

After accepting 110, we can accept any string obtained by 0 or 1.

The final regular expression is 110(0 + 1)*

The above mentioned is our first example, So we are showing the equivalence of NFA or the regular expression.

The NFA example will help a lot for the reader to understand the expression.

The below diagram shows the NFA with epsilon moves for the expression 110(0 + 1)*.

Example 2: The set of strings contain 110 as a substring.

The regular expression to accept 110 as sub string is (0 + 1)*110(0 + 1)*.

The regular expression is divided into three parts. First (0 + 1)*, second expression 110, and third expression (0 + 1)*.

The first (0+1) * says accept any string using the alphabet 0,1.

When we find the string 110, we move to the next expression.

The last (0 + 1)* says after identifying 110, any string with input symbols 0,1 is accepted.

Example 3: The set of strings contain exactly three ones.

The regular expression to accept strings containing exactly three is 0*10*10*10*.

The first 0* will accept any number of zeros.

After finding the first one, we should move to expression 0*1.

After finding one, we can take any number of zeros and follow it by one.

After finding two ones, we can take zeros and another one.

After finding three ones, we should accept only zeros.

Example 4: The set of strings contain an odd number of ones.

The regular expression to accept a string containing an odd number of ones is 0*10*(0*10*10*)*.

The regular expression before the bracket will accept a single one.

The regular expression in the brackets will accept two ones.

The expression in the bracket has a star operator. So it can repeat any number of times to accept multiples of two ones.

Finally, the expression accepts an odd number of ones.