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

 Every DFA is NFA but not vice versa

Can you please explain how this statement is true?


asked in Theory of Computation by Junior (823 points)
edited by | 81 views

From the link you gave

NFA is similar to DFA except following additional features:
1. Null (or ε) move is allowed i.e., it can move forward without reading symbols.
2. Ability to transit to any number of states for a particular input.

These are the additional benefits that NFA gives but it is not always compulsory to use them. If we don't use them then it becomes just like DFA.

But if we use these added features we can't say it is a DFA.

So we can say that NFAs can act like DFAs as well as like something more than DFAs. In this context you can think like DFA as a proper subset of NFA. 

Then " Every DFA is NFA but not vice versa" is true.



You can take analogy between an international airport(DFA) and a domestic airport(NFA). Every international airport(DFA) can be considered a domestic airport(NFA) in a way because domestic flights fly from there anyway. But every domestic airport(NFA) cannot be considered as international airport(DFA).

However unlike the analogy of airports, DFA and NFA are equivalent in power since they can be converted to each other.

1 Answer

0 votes
Generally DFA From every state on every input symbol exactly one transmission exists

Where as in Nfa More than one or none transmission exists

But Expressive powers are same
answered by (437 points)

Related questions

0 votes
1 answer
asked Nov 3, 2018 in Theory of Computation by Na462 Loyal (6.6k points) | 53 views
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
49,576 questions
54,182 answers
71,143 users