GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
18 views
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
79,843 comments
31,098 users