theory of computation

Question

The transition function of Non-deterministic push down automata is 

A) Q * $\sum$ * $\Gamma$ ----> ( 2^Q ) * $\Gamma$^*

B) Q * $\sum$ * $\Gamma$ ---->  2 ^{( Q * $\Gamma$* )}

Answer is A) or B) ...please explain your answer ...

Answer 1

we know that PDA is nothing but finite automata with stack.

So suppose finite automata is in 'Q' present state, on arriving any input (sigma) or epsilon and on checking with present state of stack alphabet  'Γ' ,finite automata decides to go on more than 1  states and push more than one symbol on the top of stack.

This is about Non Deterministic PDA

B) Q * ∑* Γ---->  2 ^{( Q * Γ* )}

^{will be answer}

Comments

how can u say PDA is finite automata?

---

Because ultimately whatever finite automata does , PDA can do also . Only difference is Automata is memory less device so it doesn't remember anything whereas PDA = finite automata  + stack , so it can able to remember that's why I m saying.