Oops! It appears that you have disabled your Javascript. In order for you to see this page as it is meant to appear, we ask that you please re-enable your Javascript!

Regular Expression Basics and rules in theory of automata

What is a regular expression?

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


What are rules for developing the 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, lets check that 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,………


More Examples:

  1. Regular Expression for the language of all those strings starting with aa and ending with ba