edited by
321 views
0 votes
0 votes

Let $N(f) =$ the class of languages accepted by Non- deterministic Finite Automata,
$N(p) =$  the class of languages accepted by Non- deterministic Push down Automata,
$D(f)=$ the class of languages accepted by Deterministic Finite Automata; and,
$D(p)=$ the class of languages accepted by  Deterministic Push down Automata.

Then, which one among these statements is TRUE?

  1. $D(f)$ subset of $N(f)$ and $D(p)$ subset of $N(p)$
  2. $D(f)$ subset of $N(f)$ and $D(p) = N(p)$
  3. $D(f) = N(f)$ and $D(p) = N(p)$
  4. $D(f) = N(f)$ and $D(p)$ subset of $N(p)$
edited by

1 Answer

Best answer
2 votes
2 votes

D is correct answer!
NFA and DFA accept the same class of language(Regular) hence both have same powers.
While DPDA accepts the proper subset(DCFL) of the language accepted by NPDA(CFL).

selected by
Answer:

Related questions

6 votes
6 votes
2 answers
1
Bikram asked Nov 26, 2016
1,174 views
Given a regular grammar $G_1$ and a context free grammar $G_2$, the problem of deciding if $L(G_1)$ is a proper subset of $L(G_2)$ is:DecidableUndecidable but semi-decida...
0 votes
0 votes
1 answer
2
Bikram asked Nov 26, 2016
294 views
$G1$ and $G2$ are regular grammars and the language generated by any grammar $G$ is represented by $L(G)$. In this case, $L(G1) \cap L(G2) = \phi$ is a/an:Decidable prob...
0 votes
0 votes
1 answer
3
Bikram asked Nov 26, 2016
202 views
Recursive Enumerable Languages are NOT closed under :UnionIntersectionComplementHomomorphism
0 votes
0 votes
1 answer
4