Regular Expression In TOC
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.
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. Following are the various examples of finite regular expressions
Example 01: Write the regular expression for the language which has no string.
Solution: Language for the given example is given below
L = { } //empty string
Regular expression for the above language is given below
L(R) = Φ
Example 02: Write the regular expression for the language with a string with zero length.
Solution: Language for the given example is given below
L = { ε } //single string
Regular expression for the above language is given below
L(R) = ε
Example 03: Write the regular expression for the language with a string with a single length over ∑ = {a, b}.
Solution: Language for the given example is given below
L = { a,b } //string with single length
A regular expression for the above language is given below
L(R) = (a+b)
Example 04: Write the regular expression for the language with a string with the length of two over ∑ = {a, b}.
Solution: Language for the given example is given below
L = (a,b).(a,b) = { aa,ab,ba,bb } //string with length of two
A regular expression for the above language is given below
L(R) = (aa+ab+ba+bb)
Example 05: Write the regular expression for the language with a string of three over ∑ = {a, b}.
Solution: Language for the given example is given below
L = (a,b).(a,b). (a,b) = { aaa,abb,aab,baa……..,bbb } //string with length of three
Regular expression for the above language is given below
L(R) = (aaa + abb + aab + baa+……..+ bbb)
Example 06: Write the regular expression for the language with strings with an at-most length of 2 over ∑ = {a, b}.
Solution: Language for the given example is given below
L = (ε,a,b).( ε,a,b) = { ε, a ,b, aa,ba……..,bb } // strings with at-most length of 2
Regular expression for the above language is given below
L(R) = (ε+a+b).( ε+a+b)
Example 07: Write the regular expression for the language with strings “Not More than two a’s and one b” over ∑ = {a, b}.
Solution: Language for the given example is given below
L = { ε, a ,b, aa,aba, aab…….. } // strings with Not More than two a’s and one b
Regular expression for the above language is given below
L(R) = { ε + a + b + aa +aba + aab+…….. }
Example 08: 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. Let explain various examples
Example 01: Write the regular expression for the language that accepts all the strings having all combinations of a’s over ∑ = {a}.
Solution: Language for the given example is given below
L = { ε, a, aa, aaa, aaaa, aaaaa, ……….. }
A regular expression for the above language is given below
L(R) = a*
Example 02: Write the regular expression for the language that accepts all the strings having all combinations of a’s except the null string over ∑ = {a}.
Solution: Language for the given example is given below
L = {a, aa, aaa, aaaa, aaaaa, ……….. }
A regular expression for the above language is given below
L(R) = a+
Example 03: Write the regular expression for the language that accepts all the strings, which has any number of a’s and b’s over ∑ = {a, b}.
Solution: Language for the given example is given below
L = {a, b, ab, ba, aab, aba, aaba ……….. }
Regular expression for the above language is given below
L(R) = (a+b)*
Example 04: Write the regular expression for the language that accepts all the strings, having only one “b” and any numbers of “a” over ∑ = {a, b}.
Solution: Language for the given example is given below
L = {b, ab, aba, abaa, abaaaa, aaaaabaaaaaaa……….. } // all strings having only one “b”
Regular expression for the above language is given below
L(R) = a*ba*
Example 05: Write the regular expression for the language that accepts all the strings, which are starting with 1 and ending with 0, over ∑ = {0, 1}.
Solution: The language for the given example is given below
L = {10, 100, 11010, 1110, 1111000, ……….. } // starting with 1 and ending with 0
Regular expression for the above language is given below
L(R) = 1(0+1)*0
Example 06: Write the regular expression for the language that accepts all the strings having even length, over ∑ = {0}.
Solution: Language for the given example is given below
L = { ε, 00, 0000, 000000, 00000000, ……….. }
Regular expression for the above language is given below
L(R) = (00)*
Example 07: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
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,
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,
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,
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.
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
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.