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.