Does `finite automaton mean deterministic finite automaton or NFA?
Since there is basically no difference between DFA and NFA (except maybe the size), we can simply speak about finite automata. Nearly every statement is true for DFA and NFA. • (P48) We say an NFA accepts a string if any one of these copies of the machine is in an accept state at the end of the input string. How about changing “any one” into “every one”? Will this new “NFA” be useful to define some kind of language? Will it be equivalent to DFA? Yes. Later we will study state minimization of DFAs. There we will define that two states p and q are equivalent if a computation started in p has the same result as a computation started in q, for all input strings. Two equivalent states can be merged into a single state. If every NFA computation must give the same result for a fixed input, then consider a state z where we have two possible successor states, i.e., two edges with the same letter label, or epsilon labels. We can just delete one of the edges (preferably the epsilon-edge). Single
