Computation Theory
Chapter Tow: Finite Automata
zied othman 3/6/22 [Course title]
Chapter Tow: Finite Automata …………………………………………………………….. Zied O. Ahmed
Chapter 2: Finite Automata
2.1 Deterministic Finite Automata
The first type of automaton we study in detail are finite Automata that are
deterministic in their operation. We start with a precise formal definition of
deterministic automata.
2.1.1 Deterministic Automata and Transition Graphs
In common with all automata, a deterministic accepter has internal states,
rules for transitions from one state to another, some input, and ways of making
decisions. All of these are incorporated in the following definition.
Definition 2.1
A deterministic finite accepter or DFA is defined by the quintuple
M = (Q,Σ,δ,q0, F),
where
Q is a finite set of internal states,
Σ is a finite set of symbols called the input alphabet,
δ: Q × Σ → Q is a total function called the transition function,
q0 ∈ Q is the initial state,
F ⊆Q is a set of final states.
A deterministic finite accepter operates in the following manner. At the
initial time, it is assumed to be in the initial state q0, with its input mechanism on
the leftmost symbol of the input string.
1
Chapter Tow: Finite Automata …………………………………………………………….. Zied O. Ahmed
During each move of the automaton, the input mechanism advances one
position to the right, so each move consumes one input symbol.
When the end of the string is reached, the string is accepted if the
automaton is in one of its final states. Otherwise, the string is rejected. The
input mechanism can move only from left to right and reads exactly one symbol
on each step. The transitions from one internal state to another are governed by
the transition function δ. For example, if
δ (q0, a) = q1,
then if the DFA is in state q0 and the current input symbol is a, the DFA
will go into state q1.
In discussing automata, it is essential to have a clear and intuitive picture to
work with. To visualize and represent finite automata, we use transition
graphs, in which the vertices represent states and the edges represent
transitions. The labels on the vertices are the names of the states, while the
labels on the edges are the current values of the input symbol.
For example, if q0 and q1 are internal states of some DFA M, then the graph
associated with M will have one vertex labeled q0 and another labeled q1. An
edge (q0,q1) labeled a represents the transition δ(q0,a) = q1. The initial state will
be identified by an incoming unlabeled arrow not originating at any vertex. Final
states are drawn with a double circle.
Example:
The graph in the Figure represents the DFA
M =({q0,q1,q2},{0, 1},δ,q0,{ql}),
where δ is given by
2
Chapter Tow: Finite Automata …………………………………………………………….. Zied O. Ahmed
This DFA accepts the string 01. Starting in state q0, the symbol 0 is read
first. Looking at the edges of the graph, we see that the automaton remains in
state q0. Next, the 1 is read and the automaton goes into state q1. We are now at
the end of the string and, at the same time, in a final state q1. Therefore, the
string 01 is accepted.
The DFA does not accept the string 00, since after reading two consecutive
0’s, it will be in state q0. By similar reasoning, we see that the automaton will
accept the strings 101, 0111, and11001, but not 100 or 1100.
It is convenient to introduce the extended transition function δ*: Q × Σ*
→ Q. The second argument of δ* is a string, rather than a single symbol, and
its value gives the state the automaton will be in after reading that string. For
example, if
δ(q0,a) = q1
and
δ(q1,b) = q2,
then
δ* (q0,ab) = q2.
3
Chapter Tow: Finite Automata …………………………………………………………….. Zied O. Ahmed
2.1.2 Languages and DFA's
The language is the set of all the strings accepted by the automaton.
The language accepted by a DFA M = (Q, Σ,δ, q0,F) is the set of all
strings on Σ accepted by M. In formal notation,
Example
Consider the DFA in Figure below. In drawing Figure, we allowed the use
of two labels on a single edge. Such multiply labeled edges are shorthand for
two or more distinct transitions: The transition is taken whenever the input
symbol matches any of the edge labels.
The automaton in the figure remains in its initial state q0 until the first b is
encountered. If this is also the last symbol of the input, then the string is
accepted. If not, the DFA goes into state q2, from which it can never escape.
The state q2 is a trap state. We see clearly from the graph that the
automaton accepts all strings consisting of an arbitrary number of a's, followed
by a single b. All other input strings are rejected. In set notation, the language
accepted by the automaton is
L = {anb:n≥0}.
4
Chapter Tow: Finite Automata …………………………………………………………….. Zied O. Ahmed
Example
Find a DFA that recognizes the set of all strings on Σ= {a,b} starting with
the prefix ab.
The only issue here is the first two symbols in the string; after they have
been read, no further decisions are needed. Still, the automaton has to process
the whole string before its decision is made. We can therefore solve the problem
with an automaton that has four states; an initial state, two states for recognizing
ab ending in a final trap state, and one nonfinal trap state.
If the first symbol is an a and the second is a b, the automaton goes to the
final trap state, where it will stay since the rest of the input does not matter. On
the other hand, if the first symbol is not an a or the second one is not a b, the
automaton enters the nonfinal trap state.
Example
Find a DFA that accepts all the strings on {0,1}, except those containing
the substring 001.
In deciding whether the substring 001 has occurred, we need to know not
only the current input symbol, but we also need to remember whether or not it
5
Chapter Tow: Finite Automata …………………………………………………………….. Zied O. Ahmed
has been preceded by one or two 0’s. We can keep track of this by putting the
automaton into specific states and labeling them accordingly. Like variable
names in a programming language, state names are arbitrary and can be chosen
for mnemonic reasons. For example, the state in which two 0’s were the
immediately preceding symbols can be labeled simply 00.
If the string starts with 001, then it must be rejected. This implies that there
must be a path labeled 001 from the initial state to a nonfinal state. For
convenience, this nonfinal state is labeled 001. This state must be a trap state,
because later symbols do not matter. All other states are accepting states.
This gives us the basic structure of the solution, but we still must add
provisions for the substring 001 occurring in the middle of the input. We must
define Q and δ so that whatever we need to make the correct decision is
remembered by the automaton. In this case, when a symbol is read, we need to
know some part of the string to the left, for example, whether or not the two
previous symbols were 00. If we label the states with the relevant symbols, it is
very easy to see what the transitions must be.
For example,
δ(00, 0) = 00
because this situation arises only if there are three consecutive 0’s. We are
only interested in the last two, a fact we remember by keeping the DFA in the
state 00. A complete solution is shown in figure below. We see from this
example how useful mnemonic labels on the states are for keeping track of
things.
Trace a few strings, such as 100100 and 1010100, to see that the solution is
indeed correct.
6
Chapter Tow: Finite Automata …………………………………………………………….. Zied O. Ahmed
2.1.3 Regular Languages
A language L is called regular if and only if there exists some deterministic
finite accepter M such that
L= L(M).
Example
Show that the language is regular.
L= {awa: w ∈ {a,b}* }
7
Chapter Tow: Finite Automata …………………………………………………………….. Zied O. Ahmed
trace a few examples to see why this works. After one or two tests, it will
be obvious that the DFA accepts a string if and only if it begins and ends with an
a. Since we have constructed a DFA for the language, we can claim that, by
definition, the language is regular.
Example
EXERCISES
1. Which of the strings 0001, 01001, 0000110 are accepted by the DFA in
Figure?
8
Chapter Tow: Finite Automata …………………………………………………………….. Zied O. Ahmed
2. For Σ= {a,b}, construct DFA's that accept the sets consisting of
(a) all strings with exactly one a,
(b) all strings with at least one a,
(c) all strings with no more than three a's,
(d) all strings with at least one a and exactly two b’s,
(e) all the strings with exactly two a’s and more than two b’s.
3. Give dfa's for the languages
(a)L= {ab5wb2: w ∈ {a,b}*},
(b)L= {abnam: n ≥ 2,m ≥3},
(c)L= {w1abw2: w1 ∈ {a,b}*,w2 ∈ {a,b}*},
(d)L= {ban: n ≥ 1,n≠ 5}.
4. With Σ = {a,b}, give a dfa for L= w1aw2: |w1|≥ 3, |w2|≤ 5}.
5. Consider the set of strings on {0,1} defined by the requirements below.
For each, construct an accepting DFA.
(a) Every 00 is followed immediately by a 1. For example, the strings 101,
0010, 0010011001are in the language, but 0001 and 00100 are not.
(b) All strings containing 00 but not 000.
(c) The leftmost symbol differs from the rightmost one.
6. Show that the language L= {vwv: v, w ∈ {a,b}*, |v|= 2} is regular.
7. Show that L= {an: n ≥4} is regular.
8. Show that the language L= {an: n ≥ 0,n ≠ 4} is regular.
9. Let L be the language accepted by the automaton in Figure. Find a DFA
that accepts L2
9
Chapter Tow: Finite Automata …………………………………………………………….. Zied O. Ahmed
2.2 Definition of a Nondeterministic Accepter
Nondeterminism means a choice of moves for an automaton. Rather than
prescribing a unique move in each situation, we allow a set of possible moves.
A nondeterministic finite accepter or NFA is defined by the quintuple
M=(Q,Σ,δ,q0,F),
where Q,Σ,q0,F are defined as for deterministic finite automata, but
Example
Consider the transition graph in Figure below. It describes a
nondeterministic accepter since there are two transitions labeled a out of q0.
10
Chapter Tow: Finite Automata …………………………………………………………….. Zied O. Ahmed
Example
A nondeterministic automaton is shown in Figure below. It is
nondeterministic not only because several edges with the same label originate
from one vertex, but also because it has a λ-transition.
Some transitions, such as δ (q2,0), are unspecified in the graph. This is to
be interpreted as a transition to the empty set, that is, δ (q2,0) = Ø. The
automaton accepts strings λ, 1010, and 101010, but not 110 and 10100. Note
that for 10 there are two alternative walks, one leading to q0, the other to q2.
Even though q2 is not a final state, the string is accepted because one walk leads
to a final state.
Example
Figure below represents an NFA. It has several λ-transitions and some
undefined transitions such as δ(q2,a).
Suppose we want to find δ* (q1,a) and δ* (q2,λ). There is a walk
labeled a involving two λ- transitions from q1 to itself. By using some of the λ
-edges twice, we see that there are also walks involving λ-transitions to q0 and
q2.
Thus,
δ*(q1,a) = {q0,q1,q2}.
11
Chapter Tow: Finite Automata …………………………………………………………….. Zied O. Ahmed
Since there is a λ-edge between q2 and q0, we have immediately that
δ*(q2,λ) contains q0. Also, since any state can be reached from itself by
making no move, and consequently using no input symbol,δ*(q2,λ) also
contains q2. Therefore,
Using as many λ-transitions as needed, you can also check that
EXERCISES
1. In Figure below, find δ* (q0,1011) and δ* (q1,01).
2. In Figure below, find δ* (q0, a) and δ* ( q1,λ).
12
Chapter Tow: Finite Automata …………………………………………………………….. Zied O. Ahmed
3. For the NFA in Figure below, find δ*(q0, 1010) and δ* (q1,00).
4. Construct an NFA with three states that accepts the language {ab,abc}*.
2.3 Equivalence of Deterministic and Nondeterministic Finite
Automata
Two finite automata, M1 and M2, are said to be equivalent if that is, if they
both accept the same language
L(M1) = L(M2),
Example
The DFA shown in Figure 1 is equivalent to the NFA in Figure 2 since they
both accept the language {(10) n : n ≥0}.
Figure 1
13
Chapter Tow: Finite Automata …………………………………………………………….. Zied O. Ahmed
Figure 2
Example
Convert the NFA in Figure below to an equivalent DFA.
The NFA starts in state q0, so the initial state of the DFA will be labeled
{q0}. After reading an a, the NFA can be in state q1 or, by making a λ-
transition, in state q2. Therefore, the corresponding DFA must have a state
labeled {q1,q2} and a transition
δ({q0},a) = {q1,q2}.
14
Chapter Tow: Finite Automata …………………………………………………………….. Zied O. Ahmed
In state q0, the NFA has no specified transition when the input is b;
therefore,
δ ({q0},b) = Ø.
A state labeled Ø represents an impossible move for the NFA and,
therefore, means nonacceptance of the string. Consequently, this state in the
DFA must be a nonfinal trap state.
We have now introduced into the DFA the state {q1,q2}, so we need to find
the transitions out of this state. Remember that this state of the DFA corresponds
to two possible states of the NFA, so we must refer back to the NFA. If the NFA
is in state q1 and reads an a, it can go to q1. Furthermore, from q1 the NFA can
make a λ-transition to q2. If, for the same input, the NFA is in state q2, then
there is no specified transition. Therefore,
δ({q1,q2},a) = {q1,q2}.
Similarly,
δ({q1,q2},b) = {q0}
At this point, every state has all transitions defined. The result, shown in
Figure below, is a DFA, equivalent to the NFA with which we started.
15
Chapter Tow: Finite Automata …………………………………………………………….. Zied O. Ahmed
Example
Convert the NFA in Figure below into an equivalent deterministic machine.
16
Chapter Tow: Finite Automata …………………………………………………………….. Zied O. Ahmed
EXERCISES
1. Convert the following NFA into an equivalent DFA.
17