Register

GATE CSE 2009 | Question: 16, ISRO2017-12

• retagged by
16,027 views
45 votes
45 votes

Which one of the following is FALSE?

  1. There is a unique minimal DFA for every regular language

  2. Every NFA can be converted to an equivalent PDA.

  3. Complement of every context-free language is recursive.

  4. Every nondeterministic PDA can be converted to an equivalent deterministic PDA.

• retagged by
User Avatar

6 Answers

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.
User Avatar
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.
User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

26 votes
26 votes
6 answers
5
Kathleen asked Sep 22, 2014
8,219 views
GATE CSE 2009 | Question: 5, ISRO2017-57
$(1217)_8$ is equivalent to $(1217)_{16}$ $(028F)_{16}$ $(2297)_{10}$ $(0B17)_{16}$
$(1217)_8$ is equivalent to$(1217)_{16}$$(028F)_{16}$$(2297)_{10}$$(0B17)_{16}$
User Avatar
34 votes
34 votes
7 answers
6
Kathleen asked Sep 22, 2014
20,797 views
GATE CSE 2009 | Question: 12, ISRO2016-37
$S \to aSa \mid bSb\mid a\mid b$ The language generated by the above grammar over the alphabet $\{a,b\}$ is the set of: all palindromes all odd length palindromes strings that begin and end with the same symbol all even length palindromes
$$S \to aSa \mid bSb\mid a\mid b$$The language generated by the above grammar over the alphabet $\{a,b\}$ is the set of:all palindromesall odd length palindromesstrings t...
User Avatar
46 votes
46 votes
7 answers
8
Kathleen asked Sep 22, 2014
21,366 views
GATE CSE 2009 | Question: 41
The above DFA accepts the set of all strings over $\{0,1\}$ that begin either with $0$ or $1$. end with $0$. end with $00$. contain the substring $00$.
The above DFA accepts the set of all strings over $\{0,1\}$ that begin either with $0$ or $1$.end with $0$.end with $00$.contain the substring $00$.
User Avatar
Link Copied!