Pushdown Automata and construct PDAin TOC

 

Pushdown automata is mathematical model of automata that is enhance version of finite automata. Finite automata with stack is called Pushdown Automata. Adding stack in the finite automata enhance the capability as compare to pushdown automata. Tape in pushdown automata is read only  memory but  stack is read-write memory. Stack memory is infinite and its operation is based on last-in-first-out.It means last object pushed on the stack is popped first. Stack memory is also known as pushdown store(PDS).

Model of Pushdown automata

Pushdown automata consist of 

• Finite tape(read only).
• Reading head(which read from the tape).
• Stack memory(Which is read/write and operated in last-in-first-out(LIFO).

Two alphabets for input symbols to be read one for input tape and another for stack. After reading the input from the tape and stack pushdown automata moves in next state write zero or more symbols on the stack.After writing on the stack the pointer to the top of the stack.This opreation is carried out for entire inputs on the tape. At the end of operation the content on the stack memory is considered as output produce by pushdown automata.

Mathmatical Discription of Pushdown Automata

Pushdown automata is described by 7-tuple(Q,Σ,Γ,δ,s,z0,F)

• Q is finite and nonempty set of states.
•  Σ is input alphabet.
•  Γ  stack alphabet.
• δ is the transition function which maps from Q *(,Σ∪ {દ}) * Γ*.
• s is the starting state.
• z0 is the starting stack symbol.
• F is the set of final state.

Example:-

Construct a pushdown automata which recognizes language L=aⁿc^mbⁿ    

Solution:

Design pushdown automata here restriction apposed on number of  a and number of b in given language it should be equal but not on the number of c. 

Store all a on the stack.

when c encountered then keep the stack unchanged.

when c encountered then match with a stored on the stack.

δ(A,a,Z0)={(A,aZ0)}

Store first a on the stack .Initially Z0 hold in stack.

δ(A,a,a)={(A,aa)}

Store remaining a on the stack. stack hold a.

δ(A,c,a)={(B,a)}

To read all c on the input tape and keep stack content unchanged.

δ(B,b,a)={(B,null)}

To match input b with a on the stack.

δ(C,b,a)={(D,null)}

To empty the stack.

When b occured all a pop from the stack .Now stack is empty  and input tape all scanned .so reach on final state D.