Register

Non-deterministic Pushdown Automata

749 views
0 votes
0 votes

Is every context-free language representable by a non-deterministic pushdown automata (using empty stack for acceptance) using only one state?

In an NPTEL lecture, a professor said this statement but I am not able to find any source verifying this statement nor I am able to come up with a solution for say, L=(anbn, n>=0), using only one state in npda using empty stack as acceptance. According to me, at least two states are required so that b comes only after a in a string. 

NPTEL video (look at 45:00) : https://www.youtube.com/watch?v=q82IcIjS1y8&list=PLbMVogVj5nJSd25WnSU144ZyGmsqjuKr3&index=33

User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

11 votes
11 votes
1 answer
1
set2018 asked Nov 1, 2017
3,431 views
deterministic pushdown automata-prefix property
How to find DPDA’s that accept by null stack? Someone explain the prefix property for DPDA,How can we use this property?
How to find DPDA’s that accept by null stack?Someone explain the prefix property for DPDA,How can we use this property?
User Avatar
0 votes
0 votes
1 answer
2
Nishtha Verma asked Aug 10, 2018
224 views
Non deterministic automata
0*1*01* Draw NFA for this?
0*1*01*Draw NFA for this?
User Avatar
0 votes
0 votes
2 answers
3
Sanjay Sharma asked Mar 31, 2017
11,218 views
deterministic and non deterministic push down automata
Which of the following is accepted by an NDPDM but not by DPDM a)All strings in which a given symbol is present at least twice b)Even length palindromes c)Strings ending with a particular terminal d)Odd length palindromes
Which of the following is accepted by an NDPDM but not by DPDMa)All strings in which a given symbol is present at least twiceb)Even length palindromesc)Strings ending w...
User Avatar
0 votes
0 votes
0 answers
4
bts1jimin asked Sep 14, 2018
312 views
Is non deterministic turing machine part of gate syllabus?
Are following part of gate syllabus? Multitape turing machine Multidimension turing machine Linear bounded automata Universal turing machine Linear bounded automata
Are following part of gate syllabus?Multitape turing machineMultidimension turing machineLinear bounded automataUniversal turing machineLinear bounded automata
User Avatar
Link Copied!