Regular Expression Basics and rules in theory of automata

Please Share This Article with Friends

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.

[quads id=1]

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. 

 

[quads id=2]

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.

 

[quads id=3]

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)

 

[quads id=4]

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
Fazal Rehman Shamil
Welcome to all friends. The reason for our success is only your love for T4Tutorials. Our team is always available to answer your queries regarding any kind of confusions or discussion regarding your study and career matters. For discussion with us please join our facebook group "T4Tutorials.com". The link of the group is mentioned below. Thanks and love to all for connecting with us. We are nothing without you. Love you all.....
https://web.facebook.com/groups/2066136233601097/