PDA vs TM and its Advantages

 

Pushdown Automata(PDA)


 

  • Pushdown automata is a way to implement a CFG in the same way we design DFA for a regular grammar. A DFA can remember a finite amount of information, but a PDA can remember an infinite amount of information.
  • Pushdown automata is simply an NFA augmented with an "external stack memory". The addition of stack is used to provide a last-in-first-out memory management capability to Pushdown automata. Pushdown automata can store an unbounded amount of information on the stack. It can access a limited amount of information on the stack. A PDA can push an element onto the top of the stack and pop off an element from the top of the stack. To read an element into the stack, the top elements must be popped off and are lost.
  • A PDA is more powerful than FA. Any language which can be acceptable by FA can also be acceptable by PDA. PDA also accepts a class of language which even cannot be accepted by FA. Thus PDA is much more superior to FA.





PDA Components:

Input tape: The input tape is divided in many cells or symbols. The input head is read-only and may only move from left to right, one symbol at a time.

Finite control: The finite control has some pointer which points the current symbol which is to be read.

Stack: The stack is a structure in which we can push and remove the items from one end only. It has an infinite size. In PDA, the stack is used to store the items temporarily.

Formal definition of PDA:

The PDA can be defined as a collection of 7 components:

Q: the finite set of states

∑: the input set

Γ: a stack symbol which can be pushed and popped from the stack

q0: the initial state

Z: a start symbol which is in Γ.

F: a set of final states

δ: mapping function which is used for moving from current state to next state.

Instantaneous Description (ID)

ID is an informal notation of how a PDA computes an input string and make a decision that string is accepted or rejected.

An instantaneous description is a triple (q, w, α) where:

q describes the current state.

w describes the remaining input.

α describes the stack contents, top at the left.

Turnstile Notation:

⊢ sign describes the turnstile notation and represents one move.

⊢* sign describes a sequence of moves.

For example,

(p, b, T) ⊢ (q, w, α)

In the above example, while taking a transition from state p to q, the input symbol 'b' is consumed, and the top of the stack 'T' is represented by a new string α.

 

Applications

For designing the parsing phase of a complier (syntax analysis).

For implementation of stack application.

For evaluating the arithmetic expressions.

For solving the Tower of Hanoi Problem.

Example 1:

Design a PDA for accepting a language {anb2n | n>=1}.

Solution: In this language, n number of a's should be followed by 2n number of b's. Hence, we will apply a very simple logic, and that is if we read single 'a', we will push two a's onto the stack. As soon as we read 'b' then for every single 'b' only one 'a' should get popped from the stack.

The ID can be constructed as follows:

1.    δ(q0, a, Z) = (q0, aaZ)  

2.    δ(q0, a, a) = (q0, aaa)  

Now when we read b, we will change the state from q0 to q1 and start popping corresponding 'a'. Hence,

1.    δ(q0, b, a) = (q1, ε)  

Thus ,this process of popping 'b' will be repeated unless all the symbols are read. Note that popping action occurs in state q1 only.

1.    δ(q1, b, a) = (q1, ε)  

After reading all b's, all the corresponding a's should get popped. Hence when we read ε as input symbol then there should be nothing in the stack. Hence the move will be:

1.    δ(q1, ε, Z) = (q2, ε)  

Where ,

PDA = ({q0, q1, q2}, {a, b}, {a, Z}, δ, q0, Z, {q2})

We can summarize the ID as:

1.    δ(q0, a, Z) = (q0, aaZ)  

2.    δ(q0, a, a) = (q0, aaa)  

3.    δ(q0, b, a) = (q1, ε)  

4.    δ(q1, b, a) = (q1, ε)  

5.    δ(q1, ε, Z) = (q2, ε)  

Now we will simulate this PDA for the input string "aaabbbbbb".

1.      δ(q0, aaabbbbbb, Z) ⊢ δ(q0, aabbbbbb, aaZ)  

  1.                     ⊢ δ(q0, abbbbbb, aaaaZ)  

3.                          ⊢ δ(q0, bbbbbb, aaaaaaZ)  

  1.                     ⊢ δ(q1, bbbbb, aaaaaZ)  

5.                          ⊢ δ(q1, bbbb, aaaaZ)  

  1.                     ⊢ δ(q1, bbb, aaaZ)  

7.                          ⊢ δ(q1, bb, aaZ)  

  1.                     ⊢ δ(q1, b, aZ)  

9.                          ⊢ δ(q1, ε, Z)  

  1.                     ⊢ δ(q2, ε)        

11.                         ACCEPT  

 

 

 

Turning machine

Turning machine was invented by Alan Turing in 1936 and it is used to accept Recursive Enumerable Languages(generated by Type-0 Grammar).

A turning machine consists of a tape infinite length on which read and writes operation can be performed. The tape consists of infinite cells on which each cell either contains input symbol or a special symbol called blank. It also consists of a head pointer which points to cell currently being read and it can move in both directions.




·       A TM is expressed as a 7-Tuple (Q,T,B, ∑,∂,q0,F) where:

·       Q is a finite set of states.

·       T is the tape alphabet(symbols which can be written on Tape)

·       B is bank symbol (every cell is filled with B except input alphabet initially)

·       ∑ is the input alphabet(symbol which are part of input alphabet)

·       
∂ is a transition function which maps Q * T        Q * T * {L, R}.Depending on its present state and present tape alphabet (pointed by head pointer),it will move to new state ,change the tape symbol (may or may not) and move head pointer to either left or right.

·       q0 is the initial state.

·       F is the set of final states. If any state of F is reached, input string is accepted.

 

 

Applications

The Church-Turing thesis claims that any computable problem can be computed by a Turing machine. This means that a computer more powerful than a Turing machine is not necessary to solve computable problems. The idea of Turing completeness is closely related to this. A system is Turing complete if it can compute every Turing computable function. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete.

To prove that something is Turing complete, it is sufficient to show that it can simulate some other Turing complete system. Usually, it is easiest to show that a system can simulate a universal Turing machine. A universal Turing machine is a Turing machine that can simulate any other Turing machine.

 

PDA Vs TM

A PDA can only access the top of its stack, whereas a TM can access any position on an infinite tape. The infinite tape cannot be simulated with a single stack , so a PDA is less computationally powerful – there are algorithms that can be programmed with a TM that cannot be programmed with a PDA.

Example 1:

Construct a TM for the language L = {0n1n2n} where n≥1

Solution:

L = {0n1n2n | n≥1} represents language where we use only 3 character, i.e., 0, 1 and 2. In this, some number of 0's followed by an equal number of 1's and then followed by an equal number of 2's. Any type of string which falls in this category will be accepted by this language.

The simulation for 001122 can be shown as below:



Now, we will see how this Turing machine will work for 001122. Initially, state is q0 and head points to 0 as:


The move will be δ(q0, 0) = δ(q1, A, R) which means it will go to state q1, replaced 0 by A and head will move to the right as:


The move will be δ(q1, 0) = δ(q1, 0, R) which means it will not change any symbol, remain in the same state and move to the right as:


The move will be δ(q1, 1) = δ(q2, B, R) which means it will go to state q2, replaced 1 by B and head will move to right as:


The move will be δ(q2, 1) = δ(q2, 1, R) which means it will not change any symbol, remain in the same state and move to right as:


The move will be δ(q2, 2) = δ(q3, C, R) which means it will go to state q3, replaced 2 by C and head will move to right as:



Now move δ(q3, 2) = δ(q3, 2, L) and δ(q3, C) = δ(q3, C, L) and δ(q3, 1) = δ(q3, 1, L) and δ(q3, B) = δ(q3, B, L) and δ(q3, 0) = δ(q3, 0, L), and then move δ(q3, A) = δ(q0, A, R), it means will go to state q0, replaced A by A and head will move to right as:


The move will be δ(q0, 0) = δ(q1, A, R) which means it will go to state q1, replaced 0 by A, and head will move to right as:


The move will be δ(q1, B) = δ(q1, B, R) which means it will not change any symbol, remain in the same state and move to right as:


The move will be δ(q1, 1) = δ(q2, B, R) which means it will go to state q2, replaced 1 by B and head will move to right as:

The move will be δ(q2, C) = δ(q2, C, R) which means it will not change any symbol, remain in the same state and move to right as:


The move will be δ(q2, 2) = δ(q3, C, L) which means it will go to state q3, replaced 2 by C and head will move to left until we reached A as:


Immediately before B is A that means all the 0's are market by A. So we will move right to ensure that no 1 or 2 is present. The move will be δ(q2, B) = (q4, B, R) which means it will go to state q4, will not change any symbol, and move to right as:


The move will be (q4, B) = δ(q4, B, R) and (q4, C) = δ(q4, C, R) which means it will not change any symbol, remain in the same state and move to right as:


The move δ(q4, X) = (q5, X, R) which means it will go to state q5 which is the HALT state and HALT state is always an accept state for any TM.



The same TM can be represented by Transition Diagram:




Authors:

Hiranmayee Sant, Abhishek Kashid, Prasanna Kshirsagar, Aniket Kulkarni, Janhavi Pawar.



Comments

Post a Comment