45 votes 45 votes Which one of the following is FALSE? There is a unique minimal DFA for every regular language Every NFA can be converted to an equivalent PDA. Complement of every context-free language is recursive. Every nondeterministic PDA can be converted to an equivalent deterministic PDA. Theory of Computation gatecse-2009 theory-of-computation easy isro2017 pushdown-automata + – Kathleen asked Sep 22, 2014 • retagged Dec 9, 2022 by Lakshman Bhaiya Kathleen 16.1k views answer comment Share Follow See 1 comment See all 1 1 comment reply Ravi_1511 commented Feb 3, 2017 reply Follow Share NFA can be drawn for Regular languages and every regular is DCFL and for each DFCL ..PDA can be drawn ..Thus NFA -> PDA 4 votes 4 votes Please log in or register to add a comment.
Best answer 54 votes 54 votes Correct Option: D NDPA is more powerful than DPDA, so they are not equivalent. Actually, DPDA is a proper subset of NDPA. C is TRUE as CFL is a proper subset of recursive languages and recursive languages are closed under complement. Bhagirathi answered Nov 25, 2014 • edited May 6, 2021 by soujanyareddy13 Bhagirathi comment Share Follow See all 9 Comments See all 9 9 Comments reply Aditya commented Jul 27, 2015 reply Follow Share what about option B ?? 0 votes 0 votes Bhagirathi commented Aug 6, 2015 reply Follow Share we can definitely convert an nfa--->dfa--->dpda 3 votes 3 votes Sushant Gokhale commented Aug 11, 2016 i edited by Sushant Gokhale Oct 30, 2016 reply Follow Share Ignore this comment. 0 votes 0 votes Sachin Mittal 1 commented Jan 23, 2017 reply Follow Share In option B, every NFA is already a PDA. Nothing to convert here. 24 votes 24 votes Ravi_1511 commented Feb 3, 2017 reply Follow Share NFA can be drawn for Regular languages and every regular is DCFL and for each DFCL ..PDA can be drawn ..Thus NFA -> PDA 5 votes 5 votes Dhiraj Raj commented Dec 7, 2018 reply Follow Share Can anyone Please explain me, why @Bhagirathi explicitly mentioned in this question that " recursive languages are closed under complement". Is this statement have to do something with this question. 0 votes 0 votes Sukhbir Singh commented Aug 23, 2019 reply Follow Share What about option a? Nfa can't be converted to pda, as pda is finite automata + a stack. 0 votes 0 votes Raj Bopche commented Jan 30, 2021 reply Follow Share @Dhiraj Raj We know that CFL’s are subset of Recursive Languages, ie every CFL is also a Recursive Language. Now one of the properties of Recursive Languages is that Complement of a Recursive Language is also Recursive, more formally Recursive Languages are closed under complementation. Hence complement of every CFL would always be Recursive. 4 votes 4 votes PreyumKr commented Jan 13 reply Follow Share CFL itself may not remain CFL after complement as CFL is not closed under complement but since its recursive and that is closed under complement hence C is true. Is that right??? 0 votes 0 votes Please log in or register to add a comment.
8 votes 8 votes The Power of NPDA is greater than DPDA, hence we cannot convert NPDA into an equivalent DPDA. Ans is D. AnilGoudar answered May 7, 2017 AnilGoudar comment Share Follow See 1 comment See all 1 1 comment reply sardendu commented Aug 23, 2018 reply Follow Share Can we say that if a cfl is subset of rec enimurable so its complement is also rec enumurable 0 votes 0 votes Please log in or register to add a comment.
6 votes 6 votes There is a unique minimal DFA for every regular language T Every NFA can be converted to an equivalent PDA. T Complement of every context-free language is recursive. T Every nondeterministic PDA can be converted to an equivalent deterministic PDA. F rishu_darkshadow answered Sep 16, 2017 rishu_darkshadow comment Share Follow See all 0 reply Please log in or register to add a comment.
4 votes 4 votes (d) Every non-deterministic PDA can be converted to an equivalent deterministic PDA anonymous answered May 7, 2017 anonymous comment Share Follow See all 0 reply Please log in or register to add a comment.
