Pumping Lemma

Pumping means jump | loop

Pumping lemma for regular set is used to find whether a given language is regular or not .

If language is regular than finite automata of that language is possible otherwise not.

If language is regular than finite auotmata of that language is possible otherwise not.

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₁

Mathematical Induction

Suppose P(N) is a statement where N is any integer and we wish to show that P(N) is true for all value of N beginning with some starting value N(o) to do this it is sufficient to show the following condition.  

1. P(No) is true  (i.e) statement is valid for No)

2. For any integer K>=No if P(k) is true than P(k+1) is also true.

Turing  Machine

Turing machine is a mathematical model having tape contain infinite number of cells.

Example Suppose (a) is string after reading a it will replace by (x) or any other character / symbol which is write operation.

R/W head is movable towards right to left or left to right. So we can say that Turing machine is two way.

Each cells contain symbols, symbol means tap symbol.

Tape symbol: Symbol stored in tap is called tape symbol.

Turing machine read tape symbol as well as write tape symbol.

Formal Definition of Turing Machine:

Turing machine is a set of seven tuples.

    Tm = (Q , Σ , 𝜏 , q0 , B , F ,δ)

        Q   → is set of states

        Σ   → is a set of input symbol such as [a,b]

        𝜏  → is a set of tape symbol such as [a,b,x,y,B]

        q0  → is a initial state.

        B   → Blank symbol (here ε is not used)

        F   → is a set of final state.

        δ : Q x 𝜏 → Q x 𝜏 (R,L)

Example : Construct a  turing machine for  aⁿbⁿ | n>=1

Solution:

            aⁿbⁿ

           L={ab, aabb, aaabbb, ......}

    Here a is replaced with suppose X and B is replaced with suppose Y.

    For understanding turing  machine let we take one example:

Initially the read write head will scan the first symbol of the input string which is a , We have to match first a and first b so for that matching process we have to use two symbols x and y. So a must be replaced by x than we move forward and c will be replaced by y.

After matching a and b we need to move left until we have seen x than again second a and b must be replaced. The above diagram show all moves and replacements.

So for doing this we need to create a turing machine table (δ) for that.

Initially turing m/c start state is q₀. First R/W head scanning symbol a towards right side as show in the above figure, now a will be replaced by x and the state will be q₁. In above table it shown.

In second move we get a so we will not change or replace tape symbol or state.

In next move (we are currently in q1 state) we get b , so we will change b to y and state to q2 and move is left move.

Same way Next Move are

Next Move

Next Move

Next Move

Next Move

Next Move

Next Move

Next Move

        Q   = {q₀, q₁, q₂, q₄}

        Σ   = {a,b}

        𝜏    = {a,b,x,y,B}

        q0 = q₀

        B   = B

        F   = {q₄}

        

Some more examples are given with solution you can download.

Finite Automata with output is always deterministic.

They are of two type:

    1. Moore Machine

    2. Mealy Machine

Moore Machine : 

Moore machine are machine in which output depends on state.

Formal Defination:

Push Down Automata is a set of seven tupples.

PDA=(Q,Σ,𝜏,q0,z0,F,δ)

where:

Q is a set of states

Σ is set of input symbol

𝜏(tau) is set of stack symbol.

q0 is initial state

z0 initial stack symbol

F set of final state

δ is transition function

PDA (Push Down Automata)

A PDA is a way to implement a CFG in a similar way we design Finite Automata for Regular Grammar.It is more powerful than Finite State Machine.It is more powerful than Finite State Machine.Finite State Machine has a very limited memory but PDA has more memory. 

PDA = FSM + Stack

# Transition function in the case of PUSH

(q,a,x) → (q',AX)

Previous top (x)

Current top (A)

Ex: (q,a,x) → (q',AX)

# Transition function in the case of POP

(q,b,A) → (q',ε)

# Skip representation

(q,x,z) → (q',z)

δ: Q x Σ x 𝜏 → Q x 𝜏*

where : 𝜏* (A,X,ε,z)

Example:

# Construct a Push Down Automata

1. {aⁿ bⁿ | n>=1}

Strings such as {ab , aabb , aaabbb ..... }

Flow chart for logic:

    δ( qₒ , a , x ) → ( qₒ , AX )

    δ( qₒ , a , A ) → ( qₒ , AA )

    δ( qₒ , b , A ) → ( q₁ , ε )

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

    δ( q₁ , ε  , x ) → POP x (Accepted)

Now here stack is empty so string is accepted.

Note: Some rejected conditions are:

1. Number of b is more than a

    δ( q₁ , b , X ) → Rejected

2. Number of a is more than b

    δ( q₁ , ε , A ) → Rejected

3. δ( qₒ , b , X ) → Rejected

4.  δ( q₁ , a , A ) → Rejected (a does not come in q₁

There are two method for implementing push down automata.

1. Empty stack method (It is a default method)

2. Final stack method

1. Empty stack method (It is a default method):

    String is accepted when scanning is completed and stack is empty

        F= φ

2. Final stack method:

    String is accepted or rejected on any final state.

        F≠ φ

Example:

Empty stack method (It is a default method)

1. Find whether aaabbb is accepted or not. 

Solution:

    δ( qₒ , aaabbb , X ) → ( qₒ , AX )

    δ( qₒ , aabbb , AX ) → ( qₒ , AAX )

    δ( qₒ , abbb , AAX ) → ( qₒ , AAAX )

    δ( qₒ , bbb , AAAX ) → ( q₁ , AAX )

    δ( q₁ , bb , AAX ) → ( q₁ , AX )

    δ( q₁ , bb , AX ) → ( q₁ , X )

    δ( q₁ , ε , X ) → POP X (Accepted)

where: 

δ: Q x ( Σ U ε ) 𝜏 → Q x 𝜏*

2. Find whether aaabb is accepted or not. 

Solution:

    δ( qₒ , aaabb , X ) → ( qₒ , AX )

    δ( qₒ , aabb , AX ) → ( qₒ , AAX )

    δ( qₒ , abb , AAX ) → ( qₒ , AAAX )

    δ( qₒ , bb , AAAX ) → ( q₁ , AAX )

    δ( q₁ , b , AAX ) → ( q₁ , AX )

    δ( q₁ , ε , AX ) → Rejected (here stack is not empty)

3. Construct a PDA for

    {aⁿ b²ⁿ | n>=1}

Strings such as { abb , aabbbb ..... }

Flow chart for logic:

3. Construct a PDA for

Flow chart for logic:

4. Construct a PDA for

Strings such as 

if w= aab than   wr (reverse of w) =bba

So string will be   

    a a b c b a a    (or)  a b b c b b a

Flow chart for logic:

δ( qₒ , a , x ) → ( qₒ , AX )

δ( qₒ , a , A ) → ( qₒ , AAX )

δ( qₒ , b , AA ) → ( qₒ , BAAX )  

δ( qₒ , c , B ) → ( q₁ , BAAX )   :No change /Skip

δ( q₁ , b , A ) → ( q₁ , AAX )   :POP B

δ( q₁ , a , A ) → ( q₁ , AX )   :POP A

δ( q₁ , a , A ) → ( q₁ , X )   :POP A

δ( q₁ , ε  , x ) → POP X (Accepted)

Suppose string is  b b a c a b b  than δ will be

δ( qₒ , b , x ) → ( qₒ , BX )

δ( qₒ , b , A ) → ( qₒ , BBX )

δ( qₒ , a , AA ) → ( qₒ , ABBX )  

δ( qₒ , c , A ) → ( q₁ , ABBX )   :No change /Skip

δ( q₁ , a , A ) → ( q₁ , BBX )   :POP A

δ( q₁ , b , B ) → ( q₁ , BX )   :POP B

δ( q₁ , b , B ) → ( q₁ , X )   :POP B

δ( q₁ , ε  , x ) → POP X (Accepted)

5. Construct a PDA for

CYK algorithm is used to check is accepted by any context free grammar or not.

CYK stands for Choche's Yonger's applied on that CFG which is Chomsky Normal Form.

Type of Grammar

1. Type 0 ( Unrestricted grammar) 

2. Type 1 (Context sensitive grammar / CSG)

3. Type 2 (Context Free Grammar / CFG)

4. Type 3 (Regular Grammar)