L = a2nbn


Consider a language, 



Design the corresponding Push Down Automata (PDA).


You should know:


Before seeing the solution please follow the previous chapter to clear the concept  (How to identify language)Language Identify: Example 




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


As per the given language alphabet ‘a’ will double of alphabet ‘b’.   


  • So, in that case, we keep unchanged whenever we will get a first ‘a’ as input.


  • But we will push a single ‘a’ when we will get a second ‘a’ as input.


  • And pop single ‘a’ from stack whenever we will get ‘b’ as input.  After scan all inputs input-tape and stack both will be empty then we can say the string is accepted otherwise rejected.


So, every time we skip for one input ‘a’ and for every second input ‘a’, we push it into the stack.






Corresponding DPDA: