Regular Expression Basics and rules in theory of automata

By: Prof. Fazal Rehman Shamil | Whatsapp:+923028700085

What is a regular expression?

Regular expressions are used to represent regular languages. If a language can’t be represented by the regular expression, then it means that language is not regular.


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. 

 


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*


Video Lecture

Download Slides

Regular Expression Basics and rules Slides PPT

List of 100+ Important Regular Expression