Theorms | TOC

Theorems 

Theorem 1: Regular expression (R.E) is closed under union operation.

Proof :

Consider a finite automata

    M₁ = (Q₁ ,  Σ₁ , q₁ , F₁ , δ₁)

    which accept L(M₁)

    such that L(M₁) = r₁

where r₁is regular expression accepted by M₁

and

    M₂ = (Q₂ ,  Σ₂ , q₂ , F₂ , δ₂)

which accept L(M₂)

such that L(M₂) = r₂

where r₁is regular expression accepted by M₂

we have to construct an finite automata 

    M = (Q ,  Σ , q₀ , {q_f} , δ)

which accept L(M)

such that L(M) = L(M₁) U L(M₂)

as follow

    (i) Q = {Q₁ U Q₂ U q₀ U q_f}

    (ii) Σ =∑₁ U ∑₂

    (iii) q₀ = q₀

    (iv)  δ is represented as

        a. δ(q₀,ε) - [q₁ , q₂]

        b. δ(f₁,ε) = δ(f₂,ε)-[q_f] 

        c. (q , a) = δ₁(q,a) (shift all transition of δ₁ to δ)

            when a∈ (∑₁ U ε) and

            for every q ∈ (Q₁ - [f₁])

        d. δ(q,a) = δ₂(q,a) when a∈(∑₂ U ε)

            and for every q∈ (Q₂ -[f₂])

 

Every transition of M₁ and M₂ is now are transition of M.

Any path in transition diagram of M from q₀ to q_f must begin by going to either q₀ or q₂ on ε. If path goes to q₁ it may follow any path from q₀ to f₁ on M₁ and finally to q_f on ε

Suppose M₁ accept a string x if path goes to q₂ it may follow any path from q₂ to f₂ on M₂ and finally to q_f on ε

Suppose M₂ accept a string y from this automata M it follow that 

L(M) = [x+y] 

            where x ∈ L(M₁) and y ∈ L(M₂)

Therefore

            if L(M) = r    ;where r is regular expression of M

            than

            r = r₁ + r₂         

Therefore Regular Expression are closed under union,  Hence Proved       

Theorem 2: Regular language are closed under concatenation

                                        OR

                    If L1 and L2 are regular than L1L2 are also regular.

Proof : 

Consider a finite automata

    M₁ = (Q₁ ,  Σ₁ , q₁ , F₁ , δ₁)

    which accept L(M₁)

    such that L(M₁) = r₁

where r₁is regular expression accepted by M₁ 

Consider another finite automata

    _{M2 = (Q2 ,  Σ2 , q2 , F2 , δ2)}

_{which accept L(M2) such that}

    _L(M2)=R2

_{where R2 is regular expression for M2}

_{we have to construct an automata} 

    _{M = (Q1 ,  Σ , q1 ,} F_{2 , δ)}

_{which accept L(M)}

_{such that} 

    _{L(M) = L(m1) . L(M2)}

_{as follow}

    (i) Q = {Q₁ U Q₂}

    (ii) Σ =∑₁ U ∑₂

    (iii) δ is represented as 

            a. δ(f₁,ε) ={q₂}

            b. δ(q,a) =  δ_{1(q₀ , a)}

                _{where a∈ (∑₁Uε) and for every}

                _{q₁∈Q₁ -{f₁}}

            _{c.  δ(q,a) = δ₂(q₁,a)}

                _{where a∈(∑₂Uε) and for every q∈Q₂}

_{If x is a string accepted by M₁ and y is a string accepted by M₂ than from the above finite automata M, it follows.}

 

        _{L(M) = {xy | x ∈ L(M1) , y ∈ L(M2)}} 

        _{Therefore  L(M) = L(M1) . L(M2)}

_{Hence Regular Expression are closed under concatenation.}

_{Hence Proved}

 

_{Theorem 3: Regular expression is closed under kleen closure.}

_Proof:

_{Consider finite automata}

     M₁ = (Q₁ ,  Σ₁ , q₁ , _{f₁} , δ₁)

which accept L(M1) such that

    L(M1) = r1

where r1 is regular expression for M1

we have to construct an automata

    M=(Q , ∑ , δ , q₀ ,{q_f})

which accept L(M) such that

    L(M) = L*(M1)

as follows

    i.  Q= { Q₁ U q₀ U q_f}

    ii. Σ = Σ₁ 

    _{iii. Transition function δ are represented as} 

        _a.  δ(q₀,ε) ={q₁ , qf }= δ(f₁,ε)

        b. shift all transition of  δ₁ to  δ

            δ(q,a) = δ₁(q,a)

        where a∈ (∑₁ U ε)

        and q ∈ (Q₁ -{f₁})

If M1 accept string x than from the finite automata (M) it follows that

    L(M) = {x* | x∈ ∑*}

Therefore L(M) = L*(M) and 

    if L(M) = r

where r is regular  expression for M than

    r=r₁*

Hence regular expression are closed under kleen closure.

Hence Proved 

 

 

_{Theorem 4: Regular expression is closed under positive closure.}

_Proof:

_{Consider finite automata}

     M₁ = (Q₁ ,  Σ₁ , q₁ , _{f₁} , δ₁)

which accept L(M1) such that

    L(M1) = r1

where r1 is regular expression for M1

we have to construct an automata

    M=(Q , ∑ , δ , q₀ ,{q_f})

which accept L(M) such that

    L(M) = L⁺(M1)

as follows

    i.  Q= { Q₁ U q₀ U q_f}

    ii. Σ = Σ₁ 

    _{iii. Transition function δ are represented as}

        a.  δ(q₀,ε)={q₁}

        b. Shift all transition of δ₁ to δ

             δ(q ,a) = δ₁(q ,a)

        where a∈ (∑₁ U ε)

        and  a∈ (Q₁ - {f₁})

If  M1 accept string x than from the finite automata (M) it follow that

    L(M) = {x⁺ | x Σ⁺}

Therefore  L(M) = L⁺(M1) and

    If L(M)=r

where r is regular expression for M than

    r=r₁⁺

Hence RE are closed under positive closure 

Hence Proved

_{Theorem 5: Construct an finite automata which accept a string does not end with 0 and 1's} 

                _OR

_{If L is regular than L' is also regular}

                _OR

_{Regular language / Expression are closed under compliment.}

_Proof:

_{Consider finite automata}

     M₁ = (Q₁ ,  Σ , q₀ , _{f₁} , δ)

which accept L

we have to construct are automata M 

    M = (Q ,  Σ , q₀ , _F , δ)

which accept L(M) such that

    L(M) = L'

    L' = Σ*-L

as follows

    i. Q = Q₁

    ii. ∑=∑₁

    iii. q₀=q₁

    iv. f=(Q-f₁)

since we have successfully constructed an automata M such as L(M)=L'

    where L'= Σ*-L

Hence proved.

 

_{Theorem 6: If L is regular L^T is also regular. (T-Transpose)}

                                    _OR

_{Regular language are closed under transpose.}

Proof:

_{Consider finite automata}

     M = (Q ,  Σ , q₀ , _F , δ)

which accept L

we have to construct are automata M'

    M' = (Q ,  Σ' , q₁ , _F' , δ')

which accept _L^T such that

as follows

    i.  Q =Q

    ii. Σ' = Σ

    _{iii. q₀' {F}}

    _{iv. F' = {q0}} 

    _{v.  δ' are represented as}

_{Consider if}  δ(A,a)→B

where  A,B ∈ Q , A ∈ (ΣUε) than

    δ'(B,a)→A

Since the new automata L' accept _L^T therefore _L^T is regular_^.

Hence Proved

 

 

_{Theorem 6: If L1 and l2 are regular language than L1∩L2 is also regular.}

Proof:

_{Consider finite automata}

     M₁ = (Q₁ ,  Σ₁ , q₁ , _F₁ , δ₁)

which accept L1 and 

Consider another automata

    M2 = (Q₂ ,  Σ , q₂ , _F₂ , δ₂)

which accept L2

we have to construct an automata

    M = (Q ,  Σ , q₀ , _F , δ)

which accept L such that

    L= L1∩L2

as follow:

    i. Q=Q₁ X Q₂

    ii. q₀ =[q₁Xq₂]

    iii. F = [F₁XF₂]

    iv. Transition δ are represented as:

        δ([p,q],a) → [x,y]  

where  δ₁(p,a)→x    and

        δ₂(q,a)→y

where p,x ∈ Q₁ , q,y ∈ Q₂ and

        a ∈ (ΣUε)

therefore M accept L such that

        L = L1∩L2

Hence L1∩L2 or L is regular

It is regular because it  is accepted by any finite automata M. 

_{Theorem 7: If L is accepted by NFA then L is also accepted by DFA.}

                            _OR

_{NFA and DFA are equivalent}

                            _OR

_{For every NFA there is  an equivalent DFA.}

Proof:

_{Consider a NDFA / NFA}

     M = (Q , Σ , q₀ , _F , δ)

which accept L(M) and 

We have to construct an equivalent DFA

    M' = (Q' ,  Σ , q₀ , F' , δ')

Which accept L(M') such that

    L(M) = L(M')

as follow:

    i. _Q=2Q

    ii. q₀' =[q₀]

    iii. F'= element of Q' which contain state of F.

    iv. δ([q₁,q₂,q₃ ----- _^qn] ,a)=[p₁,p₂,p₃ ------ _^pm]

be any transition of M than

δ' of M' are written as

    δ'([q₁,q₂,q₃ ----- q₄] ,a)= [p₁,p₂,p₃ ------ _^pm]

                    OR

    δ'([q₁,q₂,q₃ ----- q₄] ,a)= δ(([q₁],a) U ([q₂],a) U ----- U ([q_n],a))

Hence L(M) = L(M')

 

 

_{Theorem 8: For every CFG there is an equivalent PDA}             

Proof:

_{Consider a CFG}

     G = (V , T , P , S)

which accept L(M) and 

We have to construct a PDA

    P = (Q ,  Σ , Γ , q₀ , Z₀ , F , δ)

which accept L(P)

such that

    L(M) = L(P)

as follows:

    i. A →a∝

        A ∈ V , a ∈ T , ∝ ∈ V*

        δ( q₁ , a , A )→(q₁ , ∝)

    ii. A →BC

        where A , B , C ∈ V

    iii. A →BC

        where A , B , C ∈ V

        δ( q₁ , ε , A )→(q₁ , BC)

    iv. (q₀ , ε , Z₀ )→( q₁ , S , Z₀)

    v. (q₁ , ε , Z₀ )→pop Z₀  accepted

        L(M) = L(P) 

Hence Proved.

 

 

Try Some other Theorems

_{Theorem 9: For every 2-DFA there is an equivalent NFA}

 

_{Theorem 10: For every NFA with ∈ there is an equvalent NFA without ∈.}

 

_{Theorem 11: CFG are not closed under intersection , transpose and compliment.}

 

_{Theorem 12: R.E are closed under co-finite operation ⊕. In this theorem write union and intersection theorem. L₁ ⊕ L₂ mean either L₁ or L₂ or Both.} 

 

_{Theorem 13: Language accepted by R.E is regular. In this theorem we proof}  

_{R₁+R₂ | R₁.R₂  and} 

R⁺ and R^*

_{Theorem 14: Context free language are accepted by PDA or  conversion of PDA to CFG.}