# 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

**∑**consists of all strings that end in a 1. The language

^{*}1**(0∑**consists of all strings that either start with a 0 or end with a 1.

^{*})∪(∑^{*}1)Moore and Mealy Machines

Arden's Theorem