DFA and NFA -- 2

From part 1 we can recognize what DFA and NFA look like and know the equivalence between them. In “From Infinite Automata to Regular Languages” we know the equivalence between DFA, NFA and regular expressions and regular languages, and there are some tools such as pump priming and Ardens Lemma to either prove or convert them. We have made some progress in the ‘art’ level so far, so we might as well go deeper in the ‘road’ or ‘art’ level.

Why do you want to think about poor automata and regular languages? What can they be used for?

This is an “Entscheidungsverfahren”, i.e. a “judgement process”, how to determine if an existing infinite automaton or regular expression has a certain property X? This is perhaps too abstract, but let’s use a concrete problem: if there is a D, and D is a DFA or NFA or RE or rechtlineare Grammatik … , to determine the following problems: Wortproblem: to determine whether a word is recognized by D; Leerheitproblem: whether the language accepted by D is the empty set; Endlichkeitsproblem: whether the language produced by D is finite or infinite; Äquivalenzproblem: whether for D1 and D2 they are are equivalent. So how to determine that these problems are judiciable? This goes to the more central aspect of theoretical computing: if there is an algorithm that can give the correct output in finite time, then it is judiciable.

Now it is good to see the specific lemma of the above four issues：

Lemma 3.36 Das Wortproblem ist für ein Wort w und DFA M in Zeit O(|w| + |M|) entscheidbar.

Lemma 3.37 Das Wortproblem ist für ein Wort w und NFA N in Zeit O($|Q|^2$|w| + |N|) entscheidbar.

Beweis： Sei Q = {1, … ,s}, $q_0 = 1 und w = a_1 … a_n$. S:= {1} for i := 1 to n do S:= $\cup _{j \in S} \delta (j, a_i)$ return ($S \cap F \neq \emptyset$)

Lemma 3.38 Das Leerheitsproblem ist für DFAs und NFAs entscheidbar (in Zeit O(|Q||$\Sigma$|) bzw. O($|Q|^2 |\Sigma|$)).

Beweis: L(M) = $\emptyset$ gdw kein Endzustand von $q_0$ erreichbar ist. Dies ist eine einfache Suche in einem Graphen, die jede Kante maximal ein Mal benutzen muss. Ein NFA hat $\leq |Q|^2|\Sigma|$ Kanten, ein DFA hat $\leq |Q||\Sigma|$ Kanten. Ist $\Sigma$ fix, z.B. ASCII, so wird daraus O($|Q|^2$) bzw O(|Q|).

Lemma 3.39