L = anbn


Consider a language, 



Design the corresponding Push Down Automata (PDA).


You should know:


Before see the solution please follow previous chapter to clear the concept (How to identify language)




This given language is a Deterministic Context Free Language (DCFL) because it has one infinite comparison and push and pop is cleared in that case. For details see the chapter (How to identify language).


So, in that case we push ‘a’ into stack whenever we will get ‘a’ as input and we pop ‘a’ from stack whenever we will get ‘b’ as input.  After scan all inputs stack will be empty then we can say string is accepted otherwise rejected.






Because of the given language is DCFL and machine is DPDA so, there will be only one move possible for one input.


To design the DPDA for this given language we should write all the transition functions which can help us to design the machine properly.










Accepted by final and empty stack