# 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 expression are referred to as Regular languages.
- A regular expression can also be described as a sequence of pattern 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 occurrence 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.

- 1. 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.

- 1. L ⋂ M = {st | s is in L and t is in M}

**Kleen closure:** If L is a regular language then its Kleen closure L1* will also be a regular language.

- 1. L* = Zero or more occurrence 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*

That is Kleen closure of a.

### Example 2:

Write the regular expression for the language accepting all combinations of a’s except the null string, over the set ∑ = {a}

**Solution:**

The regular expression has to be built for the language

- L = {a, aa, aaa, ….}

This set indicates that there is no null string. So we can denote regular expression as:

R = a^{+}

### Example 3:

Write the regular expression for the language accepting all the string containing any number of a’s and b’s.

**Solution:**

The regular expression will be:

- r.e. = (a + b)*

This will give the set as L = {ε, a, aa, b, bb, ab, ba, aba, bab, …..}, any combination of a and b.

The (a + b)* shows any combination with a and b even a null string.

**Theory of Automata****Finite Automata****Transition Diagram****Transition Table****DFA (Deterministic finite automata)****Examples of DFA****NFA (Non-Deterministic finite automata)****Examples of NFA****Eliminating ε Transitions****Conversion from NFA to DFA****Conversion from NFA with ε to DFA****Minimization of DFA****Regular Expression****Examples of Regular Expression****Moore Machine****Mealy Machine****Context Free Grammar****Simplification of CFG****Chomsky’s Normal Form (CNF)****Greibach Normal Form (GNF)****Pushdown Automata(PDA)****Non-deterministic Pushdown Automata****Turing Machine****Examples of TM**