search
Log In
18 votes
1.3k views

Let $N_f$ and $N_p$ denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let $D_f$ and $D_p$ denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata respectively. Which one of the following is TRUE?

  1. $D_f \subset N_f \text{ and } D_p \subset N_p$

  2. $D_f \subset N_f \text{ and } D_p = N_p$

  3. $D_f = N_f \text{ and } D_p = N_p$

  4. $D_f =N_f \text{ and } D_p \subset N_p$

in Theory of Computation 1.3k views

2 Answers

21 votes
 
Best answer

Option D.

NFA and DFA both have equivalent power.(every nfa can be converted into equivalent DFA)  but NPDA can accept more languages than DPDA.


edited by
2 votes
Ans: D

Expressive power of DFA and NFA are same but not true in case of DPDA and NPDA
Answer:

Related questions

21 votes
2 answers
1
2.9k views
The following diagram represents a finite state machine which takes as input a binary number from the least significant bit. Which of the following is TRUE? It computes $1$’s complement of the input number It computes $2$’s complement of the input number It increments the input number it decrements the input number
asked Sep 22, 2014 in Theory of Computation Kathleen 2.9k views
26 votes
4 answers
2
2.2k views
Consider the languages: $L_1 = \left\{ww^R \mid w \in \{0, 1\}^* \right\}$ $L_2 = \left\{w\text{#}w^R \mid w \in \{0, 1\}^* \right\}$, where $\text{#}$ is a special symbol $L_3 = \left\{ww \mid w \in \{0, 1\}^* \right\}$ Which one of the following is TRUE? $L_1$ is a deterministic CFL $L_2$ is a deterministic CFL $L_3$ is a CFL, but not a deterministic CFL $L_3$ is a deterministic CFL
asked Sep 22, 2014 in Theory of Computation Kathleen 2.2k views
21 votes
2 answers
3
1.9k views
Let $L_1$ be a recursive language, and let $L_2$ be a recursively enumerable but not a recursive language. Which one of the following is TRUE? $L_1$' is recursive and $L_2$' is recursively enumerable $L_1$' is recursive and $L_2$' is not recursively enumerable $L_1$' and $L_2$' are recursively enumerable $L_1$' is recursively enumerable and $L_2$' is recursive
asked Sep 22, 2014 in Theory of Computation Kathleen 1.9k views
16 votes
1 answer
4
1.8k views
Which one of the following statements is FALSE? There exist context-free languages such that all the context-free grammars generating them are ambiguous An unambiguous context-free grammar always has a unique parse tree for each string of the language generated by ... pushdown automata always accept the same set of languages A finite set of string from some alphabet is always a regular language
asked Nov 2, 2014 in Theory of Computation Ishrat Jahan 1.8k views
...