# Regular Expression

The regular expressions are useful for representing certain sets of string in an algebraic fashion. Formal definition of regular expressions is as follows:â€“

Any terminal symbol, i.e. symbols Î£ including ^ and Ï† are regular expression. When, we view in Î£ as regular expression, we denote it by

- The union of two regular expressions R
_{1}and R_{2}written as R_{1}+ R_{2}also a regular expression. - 3. The concatenation of two regular expressions R
_{1}and R_{2}written as R_{1}R_{2}is also a regular expression. - The iteration of a regular expression R, written as R* is also a regular expression.
- If R is a regular expression, then (R) is also a regular expression.
- The regular expression over Î£ are precisely those obtained successively by the application of the rules 1 to 5 once or several times.

Any regular expression can be converted into a finite automation that recognizes the language, it describes and vice versa. Some basic conversions from regular expression to finite automation (M) are shown below:â€“

- If r = Îµ, M is

- If r = Ï†, M is
- If r = {a} for some a âˆˆ Î£, M is

- If r = r
_{1}+ r_{2}, then M is

- If r = r
_{1}. r_{2}, then M is

- If r = r
_{1}, then M is

Using the above basic rules / examples, any regular expression can be converted into a finite automata.

# Properties (Identities) of regular expression

- + R = R
- R + R =
- ^R = R ^ = R
- ^ * = ^ and * = ^
- R + R = R
- R * R * = R *
- RR * = R * R
- (R*)* = R*
- ^ + RR * = ^ + R * R = R*
- (PQ) * P = P (QP) *
- (P + Q)* = (P * Q*) = ( P* + Q*)*
- (P + Q) R = PR + QR and R (P + Q) = RP + RQ

** **

Construction of Finite Automata from Regular Expressions

For regular expression (a + b) the FA will be

or

For regular expression ab the FA will be

For regular expression a* the FA will be