Non deterministic pushdown automata > Deterministic pushdown automata in terms of acceptance power.

We cannot construct DPDA for WW w belongs to (a+b)+ but NPDA can be done

We cannot construct DPDA for WW w belongs to (a+b)+ but NPDA can be done

The Gateway to Computer Science Excellence

0 votes

Among Deterministic pushdown automata and Non deterministic pushdown automata, which is more powerful and why ?

0

Non deterministic pushdown automata > Deterministic pushdown automata in terms of acceptance power.

We cannot construct DPDA for WW w belongs to (a+b)+ but NPDA can be done

We cannot construct DPDA for WW w belongs to (a+b)+ but NPDA can be done

0

0 votes

In DPDAs, only one move is possible when reading any input from any state but, in NPDAs, there can be multiple moves possible for an input symbol from a state.

In **Deterministic Push Down Automata** it is always defined that at for a particular input it will be going to a specific state but in case of **Non-deterministic Push Down Automata** for a specific input it may go to different states ...

So , NPDAs are more powerful than DPDAs.

There are Context Free Languages, such as the language of palindromes, that can be accepted by NPDAs but not by DPDAs.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,741 questions

57,251 answers

198,050 comments

104,677 users