Notes on Models of Computation
Chapter 2

H. Conrad Cunningham

06 April 2022

Copyright (C) 2015, 2022, H. Conrad Cunningham
Professor of Computer and Information Science
University of Mississippi
214 Weir Hall
P.O. Box 1848
University, MS 38677
(662) 915-7396 (dept. office)

Browser Advisory: The HTML version of this textbook requires a browser that supports the display of MathML. A good choice as of April 2022 is a recent version of Firefox from Mozilla.

Note: These notes were written primarily to accompany my use of Chapter 2 of the Linz textbook An Introduction to Formal Languages and Automata [[1].

2 Finite Automata

In chapter 2, we approach automata and languages more precisely and formally than in chapter 1.

A finite automaton is an automaton that has no temporary storage (and, like all automata we consider in this course, a finite number of states and input alphabet).

2.1 Deterministic Finite Accepters

2.1.1 Accepters

Linz Definition (DFA): A deterministic finite accepter, or dfa, is defined by the tuple M=(Q,Σ,δ,q0,F)M = ( Q, \Sigma, \delta, q_{0}, F ) where

  • Q is a finite set of internal states

  • Σ\Sigma is a finite set of symbols called the input alphabet

  • δ:Q×ΣQ\delta : Q \times \Sigma \rightarrow Q is a total function called the transition function

  • q0Qq_{0} \in Q is the initial state.

  • FQF \subseteq Q is a set of final states.

A dfa operates as described in the following pseudocode:

currentState := q0q_{0}

position input at left end of string
while more input exists
currentInput := next_input_symbol
advance input to right
currentState := δ\delta(currentState,currentInput)
if currentState F\in F then ACCEPT else REJECT

2.1.2 Transition Graphs

To visualize a dfa, we use a transition graph constructed as follows:

  • Vertices represent states
    • labels are state names
    • exactly one vertex for every qiQq_{i} \in Q
  • Directed edges represent transitions
    • label on edge is current input symbol
    • directed edge (q,r)(q, r) with label aa if and only if δ(q,a)=r\delta(q,a) = r

2.1.3 Linz Example 2.1

The graph pictured in Linz Figure 2.1 represents the dfa M=({q0,q1,q2},{0,1},δ,q0,{q1})M = (\{ q_{0}, q_{1}, q_{2} \},\{ 0, 1 \},\delta, q_{0}, \{q_{1}\}), where δ\delta is represented by

δ(q0,0)=q0\delta(q_{0},0) = q_{0}, δ(q0,1)=q1\delta(q_{0},1) = q_{1}
δ(q1,0)=q0\delta(q_{1},0) = q_{0}, δ(q1,1)=q2\delta(q_{1},1) = q_{2}
δ(q2,0)=q2\delta(q_{2},0) = q_{2}, δ(q2,1)=q1\delta(q_{2},1) = q_{1}

Note that q0q_{0} is the initial state and q1q_{1} is the only final state in this dfa.

Linz Fig. 2.1: DFA Transition Graph

The dfa in Linz Figure 2.1:

  • Accepts 01, 101
  • Rejects 00, 100

What about 0111? 1100?

2.1.4 Extended Transition Function for a DFA

Linz Definition: The extended transition function δ*:Q×Σ*Q\delta^{*} : Q \times \Sigma^{*} \rightarrow Q is defined recursively:

δ*(q,λ)=q\delta^{*}(q,\lambda) = q
δ*(q,wa)=δ(δ*(q,w),a)\delta^{*}(q,wa) = \delta(\delta^{*}(q,w),a)

The extended transition function gives the state of the automaton after reading a string.

2.1.5 Language Accepted by a DFA

Linz Definition 2.2 (Language Accepted by DFA): The language accepted by a dfa M=(Q,Σ,δ,q0,F)M = ( Q, \Sigma, \delta, q_{0}, F ) is L(M)={wΣ*:δ*(q0,w)F}L(M) = \{ w \in \Sigma^{*} : \delta^{*}(q_{0}, w) \in F \}.

That is, L(M)L(M) is the set of all strings on the input alphabet accepted by automaton M.

Note that above δ\delta and δ*\delta^{*} are total functions (i.e., defined for all strings).

2.1.6 Linz Example 2.2

The automaton in Linz Figure 2.2 accepts all strings consisting of arbitrary numbers of aa’s followed by a single bb.

In set notation, the language accepted by the automaton is L={anb:n0}L = \{ a^{n}b : n \geq 0 \}.

Note that q2q_{2} has two self-loop edges, each with a different label. We write this compactly with multiple labels.

Linz Fig. 2.2: DFA Transition Graph with Trap State

A trap state is a state from which the automaton can never “escape”.

Note that q2q_{2} is a trap state in the dfa transition graph shown in Linz Figure 2.2.

Transition graphs are quite convenient for understanding finite automata.

For other purposes–such as representing finite automata in programs–a tabular representation of transition function δ\delta may also be convenient (as shown in Linz Fig. 2.3).

Linz Fig. 2.3: DFA Transition Table

2.1.7 Linz Example 2.3

Find a deterministic finite accepter that recognizes the set of all string on Σ={a,b}\Sigma = \{a, b\} starting with the prefix abab.

Linz Figure 2.4 shows a transition graph for a dfa for this example.

Linz Fig. 2.4

The dfa must accept abab and then continue until the string ends.

This dfa has a final trap state q2q_{2} (accepts) and a non-final trap state q3q_{3} (rejects).

2.1.8 Linz Example 2.4

Find a dfa that accepts all strings on {0,1}\{ 0, 1 \}, except those containing the substring 001001.

  • need to “remember” whether last two inputs were 0000

  • use state changes for “memory”

Linz Figure 2.5 shows a dfa for this example.

Linz Fig. 2.5

Accepts: λ\lambda, 0, 00, 01, 010000

Rejects: 001, 000001, 0010101010101

2.1.9 Regular Languages

Linz Definition 2.3 (Regular Language): A language L is called regular if and only if there exists a dfa M such that L=L(M)L = L(M).

Thus dfas define the family of languages called regular.

2.1.10 Linz Example 2.5

Show that the language L={awa:w{a,b}*}L = \{ awa : w \in \{ a, b \}^{*}\} is regular.

  • Construct a dfa.

  • Check whether begin/end with “a”.

  • Am in final state when second a input.

Linz Figure 2.6 shows a dfa for this example.

Linz Fig. 2.6

Question: How would we prove that a languages is not regular?

We will come back to this question in chapter 4.

2.1.11 Linz Example 2.6

Let LL be the language in the previous example (Linz Example 2.5).

Show that L2L^{2} is regular.

L2={aw1aaw2a:w1,w2{a,b}*}L^{2} = \{ aw_{1}aaw_{2}a: w_{1}, w_{2} \in \{a,b\}^{*} \}.

  • Construct a dfa.

  • Use Example 2.5 dfa as starting point.

  • Accept two consecutive strings of form awaawa.

  • Note that any two consecutive aa’s could start a second string.

Linz Figure 2.7 shows a dfa for this example.

Linz Fig. 2.7

The last example suggests the conjecture that if a language LL then so is L2L^2, L3L^3, etc.

We will come back to this issue in chapter 4.

2.2 Nondeterministic Finite Accepters

2.2.1 Nondeterministic Accepters

Linz Definition 2.4 (NFA): A nondeterministic finite accepter or nfa is defined by the tuple M=(Q,Σ,δ,q0,F)M = ( Q, \Sigma, \delta, q_{0}, F ) where QQ, Σ\Sigma, q0q_{0}, and FF are defined as for deterministic finite accepters, but

δ:Q×(Σ{λ})2Q\delta : Q \times (\Sigma \cup \{\lambda\}) \rightarrow 2^{Q}.

Remember for dfas:

  • Q is a finite set of internal states.

  • Σ\Sigma is a finite set of symbols called the input alphabet.

  • q0Qq_{0} \in Q is the initial state.

  • FQF \subseteq Q is a set of final states.

The key differences between dfas and nfas are

  1. dfa: δ\delta yields a single state
    nfa: δ\delta yields a set of states

  2. dfa: consumes input on each move
    nfa: can move without input (λ\lambda)

  3. dfa: moves for all inputs in all states
    nfa: some situations have no defined moves

An nfa accepts a string if some possible sequence of moves ends in a final state.

An nfa rejects a string if no possible sequence of moves ends in a final state.

2.2.2 Linz Example 2.7

Consider the transition graph shown in Linz Figure 2.8.

Linz Fig. 2.8

Note the nondeterminism in state q0q_{0} with two possible transitions for input aa.

Also state q3q_{3} has no transition for any input.

2.2.3 Linz Example 2.8

Consider the transition graph for an nfa shown in Linz Figure 2.9.

Linz Fig. 2.9

Note the nondeterminism and the λ\lambda-transition.

Note: Here λ\lambda means the move takes place without consuming any input symbol. This is different from accepting an empty string.

Transitions:

  • for (q0,0)(q_{0},0)?

  • for (q1,0)(q_{1},0)?

  • for (q2,0)(q_{2},0)?

  • for (q2,1)(q_{2},1)?

Accepts: λ\lambda, 10, 1010, 101010

Rejects: 0, 11

2.2.4 Extended Transition Function for an NFA

As with dfas, the transition function can be extended so its second argument is a string.

Requirement: δ*(qi,w)=Qj\delta^{*}(q_{i},w) = Q_{j} where QjQ_{j} is the set of all possible states the automaton may be in, having started in state qiq_{i} and read string ww.

Linz Definition (Extended Transition Function): For an nfa, the extended transition function is defined so that δ*(qi,w)\delta^{*}(q_{i},w) contains qjq_{j} if there is a walk in the transition graph from qiq_{i} to qjq_{j} labelled ww.

2.2.5 Language Accepted by an NFA

Linz Definition 2.6 (Language Accepted by NFA): The language LL accepted by the nfa M=(Q,Σ,δ,q0,F)M = ( Q, \Sigma, \delta, q_{0}, F ) is defined

L(M)={wΣ*:δ*(q0,w)F}L(M) = \{ w \in \Sigma^{*} : \delta^{*}(q_{0}, w) \in F \neq \emptyset \}.

That is, L(M)L(M) is the set of all strings ww for which there is a walk labeled ww from the initial vertex of the transition graph to some final vertex.

2.2.6 Linz Example 2.10 (Example 2.8 Revisited)

Let’s again examine the automaton given in Linz Figure 2.9 (Example 2.8).

Linz Fig. 2.9 (Repeated)

This nfa, call it MM:

  • must end in q0q_{0}

  • L(M)={(10)n:n0}L(M) = \{ (10)^{n} : n \geq 0 \}

Note that q2q_{2} is a dead configuration because δ*(q0,110)=\delta^{*}(q_{0},110) = \emptyset.

2.2.7 Why Nondeterminism

When computers are deterministic?

  • an nfa can model a search or backtracking algorithm

  • nfa solutions may be simpler than dfa solutions (can convert from nfa to dfa)

  • nondeterminism may model externally influenced interactions (or abstract more detailed computations)

2.3 Equivalence of DFAs and NFAs

2.3.1 Meaning of Equivalence

When are two mechanisms (e.g., programs) equivalent?

  • When they have exactly the same descriptions?

  • When they always go through the exact same sequence of steps?

  • When the same input generates the same output for both?

The last seems to be the best approach.

Linz Definition 2.7 (DFA-NFA Equivalence): Two finite accepters M1M_{1} and M2M_{2} are said to be equivalent if L(M1)=L(M2)L(M_{1}) = L(M_{2}). That is, if they both accept the same language.

Here “same language” refers to the input and “both accept” refers to the output.

Often there are many accepters for a language.

Thus there are many equivalent dfa and nfas.

2.3.2 Linz Example 2.11

Again consider the nfa represented by the graph in Linz Fig. 2.9. Call this M1M_{1}.

Linz Fig. 2.9 (Repeated): An NFA

As we saw, L(M1)={(10)n:n0}L(M_{1}) = \{ (10)^{n} : n \geq 0 \}.

Now consider the dfa represented by the graph in Linz Figure 2.11. Call this M2M_{2}.

Linz Fig. 2.11: DFA Equivalent to Fig. 9 NFA

L(M2)={(10)n:n0}L(M_{2}) = \{ (10)^{n} : n \geq 0 \}.

Thus, M1M_{1} is equivalent to M2M_{2}.

2.3.3 Power of NFA versus DFA

Which is more powerful, dfa or nfa?

Clearly, any dfa DD can be made into a nfa NN.

  • Keep the same states.
  • Define δN(q,a)={δD(q,a)}\delta_{N}(q,a) = \{ \delta_{D}(q,a) \}.

Can any nfa NN be made into a dfa DD?

  • Yes, but it is less obvious. (See theorem below.)

Thus, dfas and nfas are “equally powerful”.

Linz Theorem 2.2 (Existence of DFA Equivalent to NFA): Let LL be the language accepted by the nfa MN=(QN,Σ,δN,q0,FN)M_{N} = (Q_{N}, \Sigma, \delta_{N}, q_{0}, F_{N}). Then there exists a dfa MD=(QD,Σ,δD,{q0},FD)M_{D} = (Q_{D}, \Sigma, \delta_{D}, \{ q_{0} \}, F_{D}) such that L=L(MD)L = L(M_{D}).

A pure mathematician would be content with an existence proof.

But, as computing scientists, we want an algorithm for construction of MDM_{D} from MNM_{N}. The proof of the theorem follows from the correctness of the following algorithm.

Key ideas:

  • After reading ww, MNM_{N} will be in the some state from {qi,qj,qk}\{ q_{i},q_{j}, \ldots\ q_{k} \}. That is, δ*(q0,w)={qi,qj,qk}\delta^{*}(q_{0},w) = \{ q_{i}, q_{j}, \ldots\ q_{k} \}.

  • Label the dfa state that has accepted ww with the set of nfa states {qi,qj,qk}\{ q_{i},q_{j}, \ldots\ q_{k} \}. This is an interesting “trick”!

Remember from the earlier definitions in these notes and from discrete mathematics:

  • Σ\Sigma is finite (and the same for the nfa and dfa).

  • QNQ_{N} is finite.

  • δD\delta_{D} is a total function. That is, every vertex of the dfa graph has |Σ||\Sigma| outgoing edges.

  • The maximum number of dfa states with the above labeling is |2QN|=2|QN||2^{Q_{N}}| = 2^{|Q_{N}|}. Hence, finite.

  • The maximum number of dfa edges is 2|QD||Σ|2^{|Q_{D}|}|\Sigma|. Hence, finite.

Procedure nfa_to_dfa

Given a transition graph GNG_{N} for nfa MN=(QN,Σ,δN,q0,FN)M_{N} = (Q_{N}, \Sigma, \delta_{N}, q_{0}, F_{N}), construct a transition graph GDG_{D} for a dfa MD=(QD,Σ,δD,q0,FD)M_{D} = (Q_{D}, \Sigma, \delta_{D}, q_{0}, F_{D}). Label each vertex in GDG_{D} with a subset of the vertices in GNG_{N}.

  1. Initialize graph GDG_{D} to have an initial vertex {q0}\{ q_{0} \} where q0q_{0} is the initial state of GNG_{N}.

  2. Repeat the following steps until no more edges are missing from GDG_{D}:

    1. Take any vertex from GDG_{D} labeled {qi,qj,qk}\{ q_{i}, q_{j}, \ldots\ q_{k} \} that has no outgoing edge for some aΣa \in \Sigma.

    2. For this vertex and input, compute δN*(qi,a),δN*(qj,a),δN*(qk,a)\delta^{*}_{N}(q_{i},a),\delta^{*}_{N}(q_{j},a), \ldots\ \delta^{*}_{N}(q_{k},a). (Each of these is a set of states from QNQ_{N}.)

    3. Let {ql,qm,qn}\{ q_{l},q_{m},\ldots\ q_{n} \} be the union of all δN*\delta^{*}_{N} sets formed in the previous step.

    4. If vertex {ql,qm,qn}\{ q_{l},q_{m},\ldots\ q_{n}\} constructed in the previous step (step 2c) is not already in GDG_{D}, then add it to GDG_{D}.

    5. Add an edge to GDG_{D} from vertex {qi,qj,qk}\{ q_{i},q_{j}, \ldots\ q_{k} \} (vertex selected in step 2b) to vertex {ql,qm,qn}\{ q_{l},q_{m},\ldots\ q_{n}\} (vertex possibly created in step 2d) and label the new edge with aa (input selected in step 2b).

  3. Make every vertex of GDG_{D} whose label contains any vertex qfFNq_{f} \in F_{N} a final vertex of GDG_{D}.

  4. If MNM_{N} accepts λ\lambda, then vertex {q0}\{ q_{0} \} in GDG_{D} is also a final vertex.

This, if the loop terminates, it constructs the dfa corresponding to the nfa.

Does the loop terminate?

  • Each iteration of the loop adds one edge to GDG_{D}.

  • There are a finite number of edges possible in GDG_{D}.

  • Thus the loop must terminate.

What is the loop invariant? (This ia a property always that must hold at the loop test.)

  • If there is a walk ({q0},{qi,})(\{ q_{0}\}, \ldots\ \{ \ldots\ q_{i}, \ldots \}) in GDG_{D} labeled ww, then there is a walk (q0,qi)(q_{0}, \ldots\ q_{i}) in GNG_{N} labeled ww.

2.3.4 Linz Example 2.12

Convert the nfa in Linz Figure 2.12 to an equivalent dfa.

Intermediate steps are shown in Figures 2.12-1 and 2.12-2, with the final results in Linz Figure 2.13.

Linz Fig. 2.12: An NFA
Intermediate Fig. 2.12-1
Intermediate Fig. 2.12-2
Linz Fig. 2.13: Corresponding DFA

2.3.5 Linz Example 2.13

Convert the nfa shown in Linz Figure 2.14 into an equivalent dfa.

Linz Fig. 2.14: An NFA

δD({q0},0)=δN*(q0,0)={q0,q1}\delta_{D}(\{q_{0}\},0) = \delta^{*}_{N}(q_{0},0) = \{ q_{0}, q_{1} \}

δD({q0},1)=δN*(q0,1)={q1}\delta_{D}(\{q_{0}\},1) = \delta^{*}_{N}(q_{0},1) = \{ q_{1} \}

δD({q0,q1},0)=δN*(q0,0)δN*(q1,0)={q0,q1,q2}\delta_{D}(\{q_{0},q_{1}\},0) = \delta^{*}_{N}(q_{0},0) \cup \delta^{*}_{N}(q_{1},0) = \{ q_{0}, q_{1}, q_{2} \}

δD({q0,q1,q2},1)=δN*(q0,1)δN*(q1,1)δN*(q2,1)={q1,q2}\delta_{D}(\{q_{0},q_{1}, q_{2}\},1) = \delta^{*}_{N}(q_{0},1) \cup \delta^{*}_{N}(q_{1},1) \cup \delta^{*}_{N}(q_{2},1) = \{ q_{1}, q_{2} \}

The above gives us the partially constructed dfa shown in Linz Figure 2.15.

Linz Fig. 2.15

δD({q1},0)=δN*(q1,0)={q2}\delta_{D}(\{q_{1}\},0) = \delta^{*}_{N}(q_{1},0) = \{ q_{2} \}

δD({q1},1)=δN*(q1,1)={q2}\delta_{D}(\{q_{1}\},1) = \delta^{*}_{N}(q_{1},1) = \{ q_{2} \}

δD({q2},0)=δN*(q1,0)=\delta_{D}(\{q_{2}\},0) = \delta^{*}_{N}(q_{1},0) = \emptyset

δD({q2},1)=δN*(q2,1)={q2}\delta_{D}(\{q_{2}\},1) = \delta^{*}_{N}(q_{2},1) = \{ q_{2} \}

δD({q0,q1},1)=δN*(q0,1)δN*(q1,1)={q1,q2}\delta_{D}(\{q_{0},q_{1}\},1) = \delta^{*}_{N}(q_{0},1) \cup \delta^{*}_{N}(q_{1},1) = \{ q_{1}, q_{2} \}

δD({q0,q1,q2},0)=δN*(q0,0)δN*(q1,0)δN*(q2,0)={q0,q1,q2}\delta_{D}(\{q_{0},q_{1}, q_{2}\},0) = \delta^{*}_{N}(q_{0},0) \cup \delta^{*}_{N}(q_{1},0) \cup \delta^{*}_{N}(q_{2},0) = \{ q_{0}, q_{1}, q_{2} \}

δD({q1,q2},0)=δN*(q1,0)δN*(q2,0)={q2}\delta_{D}(\{q_{1},q_{2}\},0) = \delta^{*}_{N}(q_{1},0) \cup \delta^{*}_{N}(q_{2},0) = \{ q_{2} \}

δD({q1,q2},1)=δN*(q1,1)δN*(q2,1)={q2}\delta_{D}(\{q_{1},q_{2}\},1) = \delta^{*}_{N}(q_{1},1) \cup \delta^{*}_{N}(q_{2},1) = \{ q_{2} \}

Now, the above gives us the dfa shown in Linz Figure 2.16.

Linz Fig. 2.16: Corresponding DFA for NFA

2.4 Reduction in the Number of States in Finite Automata

This section is not covered in this course.

2.5 References

[1]
Peter Linz. 2011. Formal languages and automata (Fifth ed.). Jones & Bartlett, Burlington, Massachusetts, USA.