In the book that I am reading now, it is so easily given that "okay, let transaction function of NFA be $\delta$ and of corresponding DFA be $\delta'$, where states of the DFA are elements from the power set of states of the NFA, now let's prove they are the same". Thing is it is relatively easy to prove equivalence of existing functions by showing one-to-one correspondence than coming up with the function itself. I wonder who and how found out equivalent transition function for DFA?
2026-03-26 18:40:56.1774550456
Who first proved equivalence of NFA and DFA and how?
99 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
Nondeteminism is first introduced in "Finite Automata and their Decision Problems" by Michael Rabin and Dana Scott (1959). They also prove the equivalence with DFA's in the paper.
How I found this? It was in the introduction of the Wikipedia page on NFA's.
The thing with proofs is that it generally is relatively easy to prove something after seeing the "spark" that lights the way towards the proof. Before seeing the spark, the search for a proof will be like utter darkness, but if you practice a lot with proving things you might get a better sense of hearing, feeling and smelling, to aid in the search.