Finite Automata Regular Expression

Before explaining regular expression, we should know about regular language.

Regular Language

An alphabet ∑ is a finite set of symbols. Then, the regular languages can be -

The empty language ∅ is regular.
For each a є ∑, {a} is regular.

In the theory of computation, Grammars and Regular Expressions methods are used for generating regular language.

Regular Expression

Regular Expression has an important role in computer science applications. Basically, it is useful in the search operation, where a user searches for a particular string that satisfies certain patterns. Regular expression provides powerful functions for describing such patterns.

It is a way to represent a regular language, which is a finite set of letters. In other words, it is an algebraic description of regular languages. If r is a regular expression over some alphabet, then L(r) is the language associated with r.

Similarly, if A and B are regular expressions denoting languages L(A) and L(B) respectively, then A+B is a regular expression denoting the language L(A+B)= L(A)∪L(B). The value of a regular expression is a language.

Formal Definition of a Regular Expression

Let's say R is a Regular Expression, if R is -

a, where a is some element in the alphabet ∑ and represents the language {a},
ε, represents a language {ε},
∅, represents the empty language

and if R1 and R2 are two Regular Expressions,

R1 ∪ R2, represents the union of two regular expressions,
R1.R2, represents concatenation of two regular expressions,
R1^*, represents the Kleene star of regular expressions.

These are some valid examples of regular expressions-

Empty String - L(ε) = {ε} Empty Set - L(∅) = ∅ Single Letter - L(a) = {a} Union - L(E + F) = L(E)∪L(F) Concatenation - L(E.F) = L(E).L(F) Kleene Closure - L(E∗) = (L(E))∗ Parenthetic Expression - L((E)) = L(E).

Example of Regular Expression

Suppose, an alphabet ∑ is described as-

∑ = {0,1}

Then, the regular expression can be -

(0∪1)^*

the value of above expression is a language consisting of all possible strings of 0s and 1s. Similarly, ∑^* describes the language consisting of all strings over that alphabet. The language ∑^*1 consists of all strings that end in a 1. The language (0∑^*)∪(∑^*1) consists of all strings that either start with a 0 or end with a 1.