Regular Expressions In Automata

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

Operations on Regular Language

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

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

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

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

empty regular expression

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

regular expression (R) is equal to one input

4. The 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, the above equation shows that {a,b} is also a regular language.

Note: The 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, the above equation shows {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 occurrences 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 either finite or 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 accepts all the strings, having the length exactly two over ∑ = {a, b}.

Solution:

Language for the given example is given below

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

Regular expression for the 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 accepts all the strings, having the first symbol should be “b” and the 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