Theory of Automata

Regular Expressions In Automata



Regular expressions are used to represent the regular languages in Automata. It is also use in compiler designing.
Regular expressions are just like arithmetic, logic, Boolean expressions.

Operations on Regular Language

There may various operations on regular languages. Let “R” be a Regular expression over alphabet Sigma if R is

1. If regular expression (R) is equal to Epsilon (ε) then language of Regular expression (R) will represent the epsilon set i.e. { ε}. Mathematical equation is given below,

regular expression (R) is equal to Epsilon (ε)

2. If regular expression (R) is equal to Φ then language of Regular expression (R) will represent the empty set i.e. { }. Mathematical equation is given below,

empty regular expression

3. If regular expression (R) is equal to a input symbol “a” which belongs to sigma, then language of Regular expression (R) will represent the set which having “a” alphabet i.e. {a}. Mathematical equation is given below,

regular expression (R) is equal to one input

4. Union of two Two Regular Expressions will always produce a regular language. Suppose R1 and R2 are two regular expressions. IF R1= a, R2=b then R1 U R2 =a+b So L(R1 U R2) = {a,b}, still string “a,b” is a regular language.

Union of two Two Regular Expressions

Hence, above equation shows that {a,b} is also a regular language.

Note: Intersection of two Two Regular Expressions will always produce a regular language.



5. Concatenation of two Two Regular Expressions will always produce a regular language. IF R1= a, R2=b then R1.R2 =a.b So L(R1.R2) = {ab}, still string “ab” is a regular language

Concatenation of two Two Regular Expressions

Hence, above equation shows that {ab} is also a regular language.

6. Kleene closure of Regular Expression (RE) is also a regular language

If R1 = x and (R1)* is still a regular language

  • In a regular expression, x* means zero or more occurrence of x. It can generate { ε, x, xx, xxx, xxxx, …..}
  • In a regular expression, x+means one or more occurrence of x. It can generate {x, xx, xxx, xxxx, …..}

7. If R is regular, (R) is also a regular language

Note: Only the above mentioned 7 rules are used for regular expressions. By the combination of above 7-rules more regular Expressions can be created.

Types of Regular Expressions

As we Know regular languages are of either finite are infinite. So, Regular expressions can be written for both finite and infinite languages. So, types of Regular expressions are of two types

I. Finite Regular Expressions

Finite Regular expressions are used to represent the finite regular languages. So, the length of finite regular expressions is always limited.

For example,



Write the regular expression for the finite language which accepting all the strings, having the length exactly two over ∑ = {a, b}.

Solution:

Language for given example is given below

L = {aa, ab, ba, bb} // only 4 strings are possible for given condition

Regular expression for above language is given below

L(R) = {aa + ab +ba+bb}

II. Infinite Regular Expressions

infinite Regular expressions are used to represent the infinite regular languages. So, the length of infinite regular expressions is always unlimited.

For example,

Write the regular expression for the language which accepting all the strings, having the first symbol should be “b” and last symbol should be “a” over ∑ = {a, b}.

Solution:

Language for given example is given below

L = {ba, baa, baba, bbaa, baaaa, babbbba……….. } // unlimited strings are possible for given condition

Regular expression for above language is given below

L(R) = b (a+b)* a

Help Other’s By Sharing…

Contact Us

Burewala, Vehari, Punjab, Pakistan

cstaleem1@gmail.com

Website: CStaleem.com

Pin It on Pinterest