in Theory of Computation
389 views
1 vote
1 vote

"A DFA can simulate NFA" 

Anyone, please explain this statement in detail.

in Theory of Computation
389 views

2 Answers

2 votes
2 votes
Best answer

In simple terms “Simulate” means “Mimicry/Copy or imitate something”.

I blink an eye, you blink an eye. I walk, you walk. I run, you run.

Basically, You are simulating me. You are simulating “my behavior”.

If you can simulate each of my behavior/activity, then you are at least as powerful as me(You maybe more powerful).

But If I also can simulate each of your behavior/activity, then we are equally powerful.

For Example : Jio Chat simulates design of Whatsapp.

https://www.mensxp.com/technology/news/78092-jiochat-looks-like-a-copy-of-whatsapp-we-wonder-if-jio-spends-any-of-its-investment-on-design.html


Now, What behavior can DFA, NFA etc simulate(mimic/imitate) of each other? What do we mean by their “behavior” ?

DFAs and NFAs are computational models that solve decision problems. By their “behavior”, we mean the language they recognize.

So, When we say that “an NFA can simulate a DFA”, we mean that if we have a DFA $D$ whose language(behavior) is $L(D)$ then we can have some NFA who also has same behavior(Language).

When we say that “a DFA can simulate an NFA”, we mean that if we have an NFA $N$ whose language(behavior) is $L(N)$ then we can have some DFA who also has same behavior(Language).

So, let’s ask two questions:

$\color{red}{\text{Can DFA be simulated with an NFA ?}}$

Answer : Obviously. Every DFA is a special kind of NFA. Thus if a language $L$ is recognized by a DFA $D$, then since $D$ is a special NFA, $L$ is also recognized by an NFA.

$\color{red}{\text{Can NFA be simulated with a DFA ?}}$

Yes. We can construct a deterministic finite automaton (DFA) to simulate the NFA $N$. For any NFA $N$, We can use the “set-of-states construction/Subset Construction/Powerset Construction” to get a DFA whose language is same as the NFA $N$.

https://courses.engr.illinois.edu/cs374/fa2018/notes/models/NFAnotes.pdf

https://people.csail.mit.edu/rrw/6.045-2020/lec2-color.pdf

selected by
0 votes
0 votes
This simply means every DFA is NFA, but every NFA is not DFA

1 comment

That is a True statement but is not anywhere close in meaning to the asked question.
1
1