PDA Example

In this class, We discuss PDA Example.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of Non-Deterministic Push-Down Automata. Click Here.

Example: Take the language L = {w, where w = (a,b)* and na = nb) string length greater than zero.

The strings in the language are {ababbbaa, abab, …}

na = nb means. the number of a’s in the string should equal the number of b’s.

Logic construction:

Take an input string aabbab.

The first input symbol is a, so push onto the stack.

The second input symbol is a, and the stack top is ‘a’. So push on to the stack.

The third input symbol is b, and the stack top is a, so a pop operation is needed.

If the input is b and the stack top is a. we are removing one matching symbol.

We have seen one a and one b. cancel it in our string.

The below diagram shows the PDA for the language L.