Regular Expressions | Compiler Design - Computer Science Engineering (CSE) PDF Download

Regular Expression

• The language accepted by finite automata can be easily described by simple expressions called Regular Expressions. It is the most effective way to represent any language.
• The languages accepted by some regular expressions are referred to as Regular languages.
• A regular expression can also be described as a sequence of patterns that defines a string.
• Regular expressions are used to match character combinations in strings. String searching algorithm used this pattern to find the operations on a string.

For instance

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

Operations on Regular Language

The various operations on regular language are:

• Union: If L and M are two regular languages then their union L U M is also a union.
  L U M = {s | s is in L or s is in M}  
• Intersection: If L and M are two regular languages then their intersection is also an intersection.
  L ⋂ M = {st | s is in L and t is in M}  
• Kleene closure: If L is a regular language then its Kleene closure L1* will also be a regular language.
  L* = Zero or more occurrences of language L.  

Example 1:

Write the regular expression for the language accepting all combinations of a's, over the set ∑ = {a}
Solution: All combinations of a's means a may be zero, single, double and so on. If a is appearing zero times, that means a null string. That is we expect the set of {ε, a, aa, aaa, ....}. So we give a regular expression for this as:
R = a*  

Example 2:

Example 3: 

Examples of Regular Expression