Regular Expression Basics in theory of automata

What is regular expression?

Regular expressions are used to represent the regular languages. If a language can’t  be represented by 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 generates one a and can also generates multiple a’s together.

Note: This example is for  a+. Similarly you can generate 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 generates Null(Λ), one a and can also generates multiple a’s together.

Note: This example is for  a*. Similarly you can generate 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 lets 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