0

40kviews

Difference between PDA and NPDA

written 7.1 years ago by teamques10 ★ 70k

•   modified 7.1 years ago

Subject: Theory of Computer Science

Topic: Pushdown Automata

Difficulty: Medium

theory of computation

ADD COMMENT FOLLOW SHARE EDIT

1 Answer

1

5.7kviews

written 7.1 years ago by teamques10 ★ 70k

•   modified 7.1 years ago

PDA	NPDA
In PDA, there may exits more than one transition for each input symbol	In NPDA, there may exits exactly one transition for each input symbol.
Table may contains multiple defined entities.	Table contains single entities
There is no epsilon transition, meaning that you’re not allowed to change states without consuming anything from the input	There is epsilon transition.
Deterministic	Non deterministic
Every DPDA can be simulated by an NPDA, but the converse doesn't hold	NPDAs are a generalization of DPDAs

ADD COMMENT SHARE EDIT