DFA and NFA -- 1

Some understanding of the formal definition of DFA and NFA, as well as the proof of regular operation closure and the equivalence of DFA and NFA, that is, the story of DFA belongs to NFA, is the special case and regular story yet.

Some insights into deterministic finite automata (DFA)

For deterministic finite automatons, we can give the corresponding formal definition, borrowed here from the one given by professor in his class.

1
2
3
4
5
6
7
8

Ein deterministischer endlicher Automat (deterministic infinite automaton, DFA)
 M = (Q, ∑, δ, q0, F), besteht aus

einer endlichen Menge von Zuständen Q,
einem (endlichen) Eingabealphabet ∑,
einer (totalen!) Übergangsfunktion  δ: Q × ∑ → Q,
einem Startzustand q0 ∈ Q, und
einer Menge F ⊆ Q von Endzuständen (akzeptierenden Zust.)

This means that we first have an infinite set of states Q including all the states of the automaton, then an input alphabet ∑ including all possible inputs, a transfer function δ mapping from the present state receiving an input to a new state (there is an extended transfer function to be described later), an initial state q0 indicating where to start from, and a set F of the received states of the automaton as a subset of Q. Regarding this extended transfer function we can define it similarly:

1

δ: Q × ∑* → Q

Here ∑* represents a string consisting of ∑, which means that the automaton can also react to the input of a string, as defined for convenience. The language accepted by the device is noted as.

1

L(M):= {w∈∑*|δ(q0, w)∈F}

It means that the state in which the input string w is read from the initial state is an accepted state, and then the string is accepted. A language recognized by DFA is also called a regular language.

Some insights into non-deterministic finite automata (NFA)

For non-deterministic finite automaton the difference from deterministic lies in the non-determinism: the next state can not be uniquely determined, ε-shifts can be made, multiple choices (with 0 choices), let’s still look at the definition on Professor’s slides.

1
2
3
4
5

Ein nichtdeterministischer endlicher Automat (nondeterministic infinite automaton, NFA) ist ein 5-Tupel N = (Q, ∑, δ, q0, F), so dass
   Q, ∑, q0 und F sind wie bei einem DFA
   δ: Q × ∑ → P(Q)
   P(Q) = Menge aller Teilmengen von Q = 2^Q.
   Alternative: Relation δ ⊆ Q × ∑ × Q.

Note that the input alphabet ∑ here is the sum of the original ∑ and ε, i.e., the symbol ε of length 0 is added; then for the transfer function δ here, a symbol is read into a state in the current state, and because there are multiple choices of uncertainty, multiple states are entered, which is represented by a power set, i.e., the new state here is the state of several Qs. Similarly here for the extension of the transfer function δ one can rewrite Q as P(Q), extending the original one state to a set of several states, which constitutes a multiple backup. The language accepted by the device is noted as

1

L(N):= {w∈∑*|δ({q0}, w) ∩ F ≠ Ø}

Now it is natural to wonder what the story is between DFA and NFA, and whether DFA and NFA have the same capabilities? That is, do they recognize the same language? We know that DFA recognizes the same language that NFA recognizes, so does DFA recognize the same language that NFA recognizes? This brings us to the question of their equivalence.

Closure of regular operations

We want to go to prove the equivalence of DFA and NFA or first prove the closure of the regular operation (have time to write it again, mainly or construction method)

Equivalence of DFA and NFA

We start with a definition of “equivalence”, i.e., two machines recognize the same language, they may have the same function but different internal structure; the number of states, the transfer function may not be the same. So what we have to prove is that every NFA has equivalent DFA.(There are some digressions here. If it is a story of deterministic and non-deterministic of push-down automata or Turing machines, we need to explore it again)

Here we need to use the construction method to prove.

Proof idea: for a given NFA, construct the equivalent DFA and use the DFA to model the NFA, i.e., let the DFA remember all branches of the NFA (theoretically feasible because the k states of the NFA are infinite, and so is the subset of all possible states 2^k), while introducing the concept of ε-closure for each subset of states, the new subset of states attainable by an ε-move.

A proof is given below.

1
2
3

Say NFA N = (Q, ∑, δ, q0, F), construct DFA M = (Q', ∑, δ', q0', F'), L(M) = L(N).
Make Q' = P(Q). for R∈Q' and a∈∑, E(R)={q|Move along 0 or more ε from R up to q};
δ'(R,a)=∪(r∈R)(R ∩ F ≠ Ø).