L = anb2n


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,, ‘b’ will double of alphabet ‘a’. 


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





Answer:  Here we push two ‘a’ for a single input ‘b’.



Transition function of na = 2nb:



Corresponding DPDA: