Regular expression in automata theory with example

Finite automata is mathematical model  that  recognized  regular language.the language described by simple expression called regular expressions.Regular expressions are representation for regular language or regular set.Regular expression are used to represent set of strings in algebraic manner and describe the language accepted by finite automata.

How regular set represent in algebraic form that called regular expression.

• Regular set={} and regular expression of set  Regular expression= ф.
• Regular set={b} and regular expression of  set Regular expression=b.
• Regular set={b,a} and regular expression of  set Regular expression=b+a.
• Regular set={દ,b,bb,bbb,--------} and regular expression of  set Regular expression=b*.
• Regular set={All the world over b and a} and regular expression of  set Regular expression=(b+a)*.
• Regular set={દ} and regular expression of  set Regular expression=દ.

Find language from regular expression.

• Regular expression=ф. Regular language={}.
• Regular expression=b. Regular language={b}.
• Regular expression=b+a. Regular language={b,a}.
• Regular expression=b.a. Regular language={ba}.
• Regular expression=a+. Regular language={a,aa,aaa,aaaa,----------}.
• Regular expression=a*. Regular language={ε,a,aa,aaa,aaaa,--------}.
• Regular expression=(b+a)(a+b). Regular language={ba,bb,aa,ab}.
• Regular expression=(a+b)*.

         if  *  is 0 we get  ε.

         if  *  is 1 we get  a,b.

         if * is 2  we get (a+b)(a+b)=aa,ab,ba,bb.

         

     so Regular language of regular expression (a+b)*  is (ε,a,b,aa,ab,ba,bb,------------).

• Regular expression=a*.a*.

         if  *  is 0 we get  ε.

         if  *  is 1 we get  a.

         if * is 2  we get  aa.

        = (ε,a,aa,------) (ε,a,aa,------)

        =( ε,a,aa,aaa,aaaa,-----------).

    Hierarchy  of Evaluation of Regular Expression

1. Parenthesis.
2. Kleene closure.
3. Concatenation.
4. Union.

Example.

Consider Regular Expression  (a+b)*abb. Find corresponding Regular set.

Solution

According to the  Evaluation hierarchy of regular expression first evaluate (a+b)*

if * is 0 then get ε.

if * is 1 then get a,b.

if * is 2 then get (a+b)(a+b)=aa,ab,ba,bb.

we get (ε,a,b,aa,ab,ba,bb)

={ε,a,b,aa,ab,ba,bb,----------}abb

={abb,aabb,babb,aaabb,ababb,baabb,bbabb,--------}

=All the string over{a,b} ending in "abb"

Identities for Regular Expressions

• ф+R=R

        prove L.H.S=R.H.S

         L.H.S= ф+R

           ={}+R

          =R

        L.H.S=R.H.S

• (R*)*=R*

         =({ε,R,RR,RRR,--------})*

         = {ε,R,RR,RRR,---------)

         =R*

          L.H.S=R.H.S

• RR*=R+

       =R{ε,R,RR,RRR,-----------}

       = R,RR,RRR,RRRR,---------

       =R+

          L.H.S=R.H.S

• εR=R

        =Concatenation of  ε with any string result in the same string.

        =R

        L.H.S=R.H.S

• фR=ф

         ={}R       ф means no element

         ={}

         =ф

         L.H.S=R.H.S