# Regular Expression Basics and rules in theory of automata

By Prof. Fazal Rehman Shamil

## What is a regular expression?

Regular expressions are used to generate patterns of strings. A regular expression is an algebraic formula whose value is a pattern consisting of a set of strings, called the language of the expression.

## What are the rules for developing regular expressions?

Rule 1:

R.E =  a+

Strings = a, aa, aaa, aaaa, aaaaa,……….

Explanation: It can generate one a and can also generate multiple a’s together.

Note: This example is for  a+. Similarly, you can generate the regular expression for any other alphabet like b+, c+, 0+ or 1 and for any other alphabet.

• When + is used as a power, then it represents a loop that can run null time or any time.
• When + is used as an operator between operands, then it represents the or operator with the help of which we can chose the right side or left side.

Rule 2:

R.E =  a*

Strings = Λ, a, aa, aaa, aaaa, aaaaa,……….

Explanation: It can generate Null(Λ), one a and can also generates multiple a’s together.

Note: This example is a*. Similarly, you can generate a regular expression for any other alphabet like b*, c*, 0or 1 and for any other alphabet.

Rule 3:

R.E =  (a+b)

Explanation: It can generate only one a or it can generate only one b. Nothing else.

Strings = a, b

Rule 4:

Every string that is part of the language should be accepted by the R.E and every string that is not part of the language should be rejected by the R.E.

• If 99% strings that are part of the language and are accepted by the R.E and if only 1% string is the string that is part of the language and is rejected by the R.E, then R.E is still wrong.
• If 99% strings that are not part of the language and are rejected by the R.E and if only 1% string is the string that is not part of the language and is accepted by the R.E, then R.E is still wrong.

For example;

Language = language of all those strings starting with a, defined over ∑=(a,b)

Accepted strings: a, aa, aba…………

Rejected strings: b, ba, bb, bab, ………

R.E =a(a+b)*

Practice:

Now, let’s check how strings can be accepted by R.E.

R.E =a(a+b)*

Strings: aaa, ab, aab, aaab, aba, ababab,………

Similarly, another example is

Language= language of all those strings starting with b, defined over ∑=(a,b)

Accepted strings: b, ba, bb, bab,…………

Rejected strings: a, aa, ab, aba,……..

R.E = b(a+b)*

Practice:

Now let us check that how strings can be accepted by R.E

R.E =b(a+b)*

Strings: bba, bb, bab, baab, bba, bbabab,………

A regular expression for the language of all those strings in which NO bab occurs in the string. defined over {a,b}

solution: R.E= b*a*

A regular expression for the language of all those strings in which NO bab occurs in the string. defined over {a,b}
solution:  R.E= a*b*a*

Regular expression for the set of all strings of a’s and b’s that have at least 2 a’s.

(a+b)* a (a+b)* a (a+b)*

Valid strings={aa, aaa, baa,aab, aba, abba,…}

InValid strings={a, b, baa,abb, abb, abbb,…}

Regular expression for the set of all strings whose first symbol from the right end is a 0.
L = (0+1)*0
Regular expression for the set of all strings whose second symbol from the right end is a 0.
L = (0+1)*.0.(0+1)
Regular expression for the set of all strings whose 3rd symbol from the right end is a 0.
L = (0+1)*.0.(0+1).(0+1)

Describe the strings that are represented by the regular expression (0+1)*.0.(0+1).(0+1).

Valid Strings={0000,1000, 1010, and many other similar strings}

Regular expression for the strings that do not contain a as a string defined over {a,b}

(b)*

Regular expression for the strings that do not contain single a as a string defined over {a,b}

(aa+b)*

A regular expression for the language of all
those strings having even length strings and
starting with a
or
odd length strings
starting with b

RE = a(aa+bb+ab+ba)*(a+b) + b(aa+bb+ab+ba)*

## Video Lecture

Regular Expression Basics and rules Slides PPT Turing Machine Comparison with Regular Expression , CFG, PDA and Deterministic Finite Automata

## Tutorial: Regular Expression

A detailed tutorial of the regular expression is here in the link of regular expression tutorial. This page contains the practice questions of regular expressions with solutions.

Tutorial covering the topics

• Give a regular expression.
• Describe the strings of the regular expression.
• write a regular expression.
• create all strings from regular expression.
• Generate all strings from regular expression.
• Extract all strings from regular expression.
• Find all strings from regular expression.
• Examples of regular expression.
• What is * in regular expression?
• What does + mean in regular expression?
• What is a “.” in regular expression?
• What does the regular expression r=(a+b+c)*? Prof.Fazal Rehman Shamil (Available for Professional Discussions)
1. Message on Facebook page for discussions,