FOR FREE MATERIALS

Example: 

L = ${\mathbf{n}}_{\mathbf{a}}\mathbf{\left(}\mathbf{\omega }\mathbf{\right)}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{n}}_{\mathbf{b}}\mathbf{\left(}\mathbf{\omega }\mathbf{\right)}$

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), Identification of language Example 2.

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 details see the Identification of language Example 2).

The given language is a set of all strings generated by ‘a’ and ‘b’ where number of a = number of b.

• In that case, initially, the stack is empty we push the first input alphabet from the input-tape either ‘a’ or ‘b’.

• After that, we check input tape and Top of the Stack (TOS). If both are the same we push current input to stack (‘a’ or ‘b’) or if both are not the same we pop alphabet (‘a’ or ‘b’) from TOS for the current input (‘a’ or ‘b’) at input tape.

Let take an example, ω = a a b b b b a b a a. Here number of a and b is same.

Corresponding DPDA: