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}$

4 - Examples of regular expressions

Post Views: 53

By My- Courses

Automata theory and formal language

Regular ( or rational ) Expression

1 - Regular Expression Overview

2 - Use of regular expressions

3 - Definition of regular expressions

4 - Examples of regular expressions

By My- Courses

Related Post

Sum and Product of Automata

Introduction to finite deterministic automata

Algebraic Grammar

Leave a Reply Cancel reply

You missed

Solution Exercise 84 : Python Function for Finding Repeated Characters in a String

Solution Exercise 83 : python algorithm that determines the first repeated character within a given string

Solution Exercise 82 : Removing Empty Strings from a List

Solution Exercise 81 : Python Word Frequency Analysis in dictionary