REGULAR EXPRESSIONS

    

 About R.E's. :-

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

What are Regular Languages? 

– An alphabet Σ = {a, b, c} is a finite set of letters,

– The set of all strings (aka, words) Σ∗ over an alphabet Σ can be recursively defined as:- 

:Base case: ε ∈ Σ ∗ (empty string), 

:Induction: If w ∈ Σ ∗ then wa ∈ Σ ∗ for all a ∈ Σ. 

– A language L over some alphabet Σ is a set of strings, i.e. L ⊆ Σ ∗ . Some examples: – Leven = {w ∈ Σ ∗ : w is of even length} – La∗b∗ = {w ∈ Σ ∗ : w is of the form a n b m for n, m ≥ 0} 

– La nb n = {w ∈ Σ ∗ : w is of the form a n b n for n ≥ 0} – Lprime = {w ∈ Σ ∗ : w has a prime number of a 0 s} 

– Deterministic finite state automata define languages that require finite resources (states) to recognize. 

Why they are “Regular”? 

– A number of widely different and equi-expressive formalisms precisely capture the same class of languages: 

– Deterministic finite state automata. 

– Nondeterministic finite state automata (also with ε-transitions). 

– Kleene’s regular expressions, also appeared as Type-3 languages in Chomsky’s hierarchy. 

– Monadic second-order logic definable languages. 

– Certain Algebraic connection (acceptability via finite semi-group). 

Example:-

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.

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.

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.

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* i.e. 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, aaaa, .......}

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=(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.