Regular ( or rational ) Expression

Dec 7, 2017

1 - Regular Expression Overview

2 - Use of regular expressions

3 - Definition of regular expressions

$subsection{Definition of rational (regular) expression} Let now $ Sigma $ a finite alphabet and $underline{Sigma }$ a copy of $% Sigma .$ We can then define a textbf{regular expression} textbf{RE} ( called also textbf{rational expression} ) recursively as follow : begin{definition} A regular expression is a word of $underline{Sigma }cup {(,),+,cdot ,ast }$ such that the set textbf{RE} of regular expressions satisfy the following axiomes :newline $1-$ $ emptyset $ and $underline{a}in RE$ for all $ain Sigma $newline $2-$ If $E$ $ and F$ are tow regular expressions in $RE$ then $% E+F,E.F$ and $E^{ast }$ are also. end{definition} Now we can define a mono"{i}de morphisme $M:RElongrightarrow P(Sigma ^{ast })$ by posing : begin{eqnarray*} M(emptyset ) &=&{emptyset }text{ }andtext{ }M(a)={a} \ M(E+F) &=&M(E)cup M(F) \ M(E.F) &=&M(E).M(F) \ M(E^{ast }) &=&(M(E))^{ast } end{eqnarray*} Thus we can deduce : begin{theorem} A language $L$ over $Sigma $ is rational ( regular ) if and only if there exists a regular expression $E$ such that $L=M(E)$ end{theorem}$