First time here? Checkout the FAQ!
+1 vote
What is main difference between Deterministic Push down automata and simple Push down automata ?
asked in Theory of Computation by (127 points)   | 18 views

1 Answer

0 votes

In computer science, a pushdown automaton(PDA) is a type of automaton that employs a stack. Pushdown automata are used in theories about what can be computed by machines. They are more capable than finite-state machines but less capable than Turing machines.


deterministic pushdown automaton  is a variation of the pushdown automata. The class of deterministic pushdown automata accepts the deterministic CFL a proper subset of context free language.

answered by Active (1.8k points)  
Which kind of proper subsets of CFL can be accepted by DPDA ?
A deterministic push down automata is a push down automata than never had a choice in its move.

Eg- a^nb^n n>=0 dpda and cfl

Whereas ww^r is cfl but npda

Top Users Sep 2017
  1. Habibkhan

    7096 Points

  2. Warrior

    2574 Points

  3. Arjun

    2412 Points

  4. rishu_darkshadow

    2402 Points

  5. A_i_$_h

    2204 Points

  6. nikunj

    1980 Points

  7. manu00x

    1846 Points

  8. makhdoom ghaya

    1760 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points

26,115 questions
33,691 answers
31,098 users