The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+17 votes

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 by Veteran (52.1k points) | 790 views

2 Answers

+19 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.

by Active (3.5k points)
edited by
+2 votes
Ans: D

Expressive power of DFA and NFA are same but not true in case of DPDA and NPDA
by Loyal (7.1k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,309 questions
55,742 answers
90,455 users