0 votes 0 votes Every DFA is NFA but not vice versa Can you please explain how this statement is true? Reference:- https://www.geeksforgeeks.org/toc-finite-automata-introduction/ Theory of Computation theory-of-computation finite-automata + – dan31 asked Aug 28, 2018 • edited Aug 28, 2018 by Shaik Masthan dan31 2.9k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply MiNiPanda commented Aug 28, 2018 reply Follow Share 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. 0 votes 0 votes Mizuki commented Aug 29, 2018 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.
0 votes 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 Deepak Raj 1 answered Aug 28, 2018 Deepak Raj 1 comment Share Follow See all 0 reply Please log in or register to add a comment.