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 15.7k 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.
2 votes 2 votes Deterministic PDA cannot handle languages or grammars with ambiguity. nondeterministic can handle languages with ambiguity and any context-free grammar. Therefore, every nondeterministic PDA cannot be converted to an equivalent deterministic PDA. pankaj_vir answered Mar 12, 2018 pankaj_vir comment Share Follow See 1 comment See all 1 1 comment reply Ekta07_GATE commented Jan 6, 2019 reply Follow Share https://gateoverflow.in/6370/complement-contet-language-recursive-recursive-enumerable 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes As we know there are several languages (CFL) for which we only have NPDA, i.e. these languages cannot be recognized by DPDA. For example L= {$w^{}$$w^{r}$ | w ϵ {a,b}* } is a CFL but not DCFL, i.e. it can be recognized by NPDA but not by DPDA. King Suleiman answered Jul 23, 2019 King Suleiman comment Share Follow See all 0 reply Please log in or register to add a comment.
