The Gateway to Computer Science Excellence
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 (147 points) | 75 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 Loyal (3.1k 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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,946 questions
36,792 answers
34,688 users