Discussion
Which ONE of the following languages is accepted by a deterministic pushdown automaton?
Answer: A
A deterministic pushdown automaton can accept any regular language.
Every regular language has a deterministic finite automaton, and a DPDA can simulate a DFA by simply never using its stack. So every regular language is a deterministic context-free language.
The reverse does not hold for the other classes. Some context-free languages, such as even-length palindromes, need nondeterminism (the machine must guess the middle), so not every context-free language, or every language of a nondeterministic PDA, is accepted by a DPDA. Decidable languages include non-context-free ones such as anbncn, which no pushdown automaton accepts.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development