FOR FREE CONTENT

Example: 

L = ${\mathbf{a}}^{\mathbf{m}}{\mathbf{b}}^{\mathbf{n}}\mathbf{,}\mathbf{ }\mathbf{m}\mathbf{ }\mathbf{\ne }\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 

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 m ≠ n means m > n or m < n. 

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 input tape has some alphabet ‘b’ and stack will be empty then the string will be accepted otherwise rejected. 

Example: 

Either, 

Corresponding DPDA: