Regular Expressions
Regular expressions are also referred as rational expressions, which are used to describe the algebraic description of regular languages. It is generally a sequence of characters that is used to find a string in language. Regular expressions play an important role in computer science applications, which involves:
Like other expressions, such as arithmetic expressions, logical expressions etc., regular expression also have permitted symbols and operators. Only defined symbols can be used to build a regular expression. For example:
(a U b) a*
The regular expression has two parts:
First is (a U b) and second is a*
The symbols a and b are shorthand for sets {a} and {b}. In this (a U b) means ({a} U {b}). In this, {a, b} and {a}* means that the language consisting of all strings having any number of a’s (e.g. ε, a, aa….}.
Both expressions and parts are combined to form the value of the entire expression.
Formal Definitions Used in Regular Expression
Let R be a regular expression over alphabet ∑, then:
Note: Do not confuse with regular expression ε and Φ. The expression ε denotes the language containing only a single string, or we can say that empty string. On the other hand Φ represents the language that does not contain any strings.
Operators used in Regular Expression
We have following permitted operators for building regular expressions:
Union:
The Union of two languages P and Q is denoted by P U Q, which is the set of strings that are in either P or Q or in both.
Example:
If P = {1, 2} and Q = {a, b}
P U Q = {1, 2, a, b}
Concatenation:
The Concatenation of two languages P and Q is denoted by P.Q, which is the set of strings that can be formed by taking any string in P concatenating it with any string in Q.
Example:
If P = {a, b} and Q = {ε, d}
P.Q = {a, b, ad, bd}
Closure:
The closure of a language P is denoted by P*, which defines the set of those strings that can be formed by taking any number of strings from P with repetitions and concatenations of strings.
Example:
If P = {1, 2}*
P= {ε, 1, 2, 11, 22, ………..}
Precedence of Regular Expression Operators
If we are using parenthesis with regular expressions, then the evaluation of regular expression is performed on the basis of operator’s precedence. For Regular expression, the order of precedence is given below:
Examples of Regular Expression
Example 1:
Consider the alphabet ∑ = {a, b}, and describe the regular expression set for all strings having a single b.
Solution:
The regular expression will be:
R = a*ba*
Example 2:
Consider the alphabet ∑ = {a, b}, and describe the regular expression set for all strings having bbbb as substring.
Solution:
The regular expression will be:
R = (a+b)* bbbb (a+b)*
Example 3:
Consider the alphabet ∑ = {a, b}, and describe the regular expression set for all strings ends with ab.
Solution:
The regular expression will be:
R = (a+b)*ab
Example 4:
Consider the alphabet ∑ = {a, b, c}, and describe the regular expression set for all strings, which contain no more than three b’s.
Solution:
The regular expression will be:
R = (ε +b) (ε +b) (ε +b)
This regular expression describes the string containing zero, one, two or three b’s and nothing else.