Question

Construct a PDA for the language of all non-palindromes over {a, b} (accept
by empty stack) and convert it into accept by final state.

Answer 1

Answer:

A Pushdown Automaton (PDA) is like an epsilon Non deterministic Finite Automata (NFA) with infinite stack. PDA is a way to implement context free languages. Hence, it is important to learn, how to draw PDA.

Here, take the example of odd length palindrome:

Que-1: Construct a PDA for language L = {wcw’ | w={0, 1}*} where w’ is the reverse of w.Approach used in this PDA –

Keep on pushing 0’s and 1’s no matter whatever is on the top of stack until reach the middle element. When middle element ‘c’ is scanned then process it without making any changes in stack. Now if scanned symbol is ‘1’ and top of stack also contain ‘1’ then pop the element from top of stack or if scanned symbol is ‘0’ and top of stack also contain ‘0’ then pop the element from top of stack. If string becomes empty or scanned symbol is ‘$’ and stack becomes empty, then reach to final state else move to dead state.