FOR FREE YEAR SOLVED

Example: 

L = ${\mathbf{a}}^{\mathbf{m}}{\mathbf{b}}^{\mathbf{n}}\mathbf{,}\mathbf{ }\mathbf{m}\mathbf{ }\mathbf{\ge }\mathbf{ }\mathbf{n}$

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 greater than or equal to the number of ’b’ in all strings belongs to this given language.

So, in that case, two circumstances can happen

1. ${\mathbf{a}}^{\mathbf{m}}{\mathbf{b}}^{\mathbf{n}}\mathbf{,}\mathbf{ }\mathbf{m}\mathbf{ }\mathbf{>}\mathbf{ }\mathbf{n}$ : In that case after all push and pop operations if input tape has empty but the stack has one or more alphabet ‘a’ then we can say the string is accepted otherwise rejected.

                        OR

2. ${\mathbf{a}}^{\mathbf{m}}{\mathbf{b}}^{\mathbf{n}}\mathbf{,}\mathbf{ }\mathbf{m}\mathbf{ }\mathbf{=}\mathbf{ }\mathbf{n}$ : In that case after all push and pop operations if both input tape and stack will be empty then the string will be accepted otherwise rejected.

Example: 

Either,

Corresponding DPDA: