Question

a.What is the main factor that makes a PDA unable to recognize certain languages?

Answer 1

Push Down Automata (PDA):The formal description of PDA has 7 tuples.

They are (Q,,,q₀,Z₀,F,)

• Q is the finite set of all states
• is the finite set of Input Alphabet
• is the finite set of Stack Alphabet
• q_{0 is the start state}
• Z_{0 is the start of stack Symbol}
• F is the set of Final states
• is the Transition Function.

Note: A Push Down Automata is a Finite Automata with Stack.Unlike Finite state Automata PDA has Memory but less limited Memory.

A PDA(Deterministic Push Down Automata) can recognize only certain Context free Languages only As it have very Limited Memory which won't be enough for Uncertain Context free languages.To over come this we have Turing Machines.

For Example: A PDA cannot recognize a Even palindrome As it cannot remember the Number of 1's and 0's before.

If You Have Any Doubts. Please Ask Using Comments.

Have A Great Day!