# GATE2005-54

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$

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
Ans: D

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

## Related questions

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
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
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