L =
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 9, Language Identify: Examples 12
Solution:
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 more details see the above links)
As per the given language number of ‘a’ is less than the number of ’b’ in all strings belongs to this given language.
So, in that case, we push ‘a’ into the stack whenever we will get ‘a’ as input and we pop ‘a’ from the stack whenever we will get ‘b’ as input. After scanning all inputs if the input tape has still some number of ‘b’ but the stack is empty then we can say the string is accepted otherwise rejected.
Example:
Corresponding DPDA: