GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
156 views
Which one is more powerful Deterministic push down automata or Non Deterministic push down automata ?
asked in Theory of Computation by (39 points)   | 156 views

3 Answers

+5 votes
Best answer
NPDA(Non Deterministic Push Down Automata) is more powerful than DPDA(Deterministic Push Down Automata).

for eg: There are languages for which we can make NPDA but DPDA can not be possible...

L = { WW^r   | W belongs to (a + b)^(+) }
answered by Veteran (14.5k points)  
selected by
+3 votes
expressive power of DPDA < expressive power of NPDA

ie. language accpeted by deterministic PDA is greater then Non deterministic PDA

therefore NPDA is more powerful then DPDA
answered by Loyal (3.1k points)  
+1 vote
non deterministic push down automata is more powerfull
answered by (49 points)  


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