# Deterministic Finite Automata

A finite automaton, FA, provides the simplest model of a computing device. It has a *central processor* of finite capacity and it is based on the concept of *state*. It can also be given a formal mathematical definition . Finite automata are used for pattern matching in text editors, for compiler lexical analysis.

Another useful notion is the notion of nondeterministic automaton.

We can prove that deterministic finite automata, DFA, recognize the same class of languages as NDFA, i. e. they are equivalent formalisms.

It is also possible to prove that given a language `L`

there exists a unique (up to isomorphism) minimum finite state automaton that accepts it, i.e. an automaton with a minimum set of states.

The automata in the examples are deterministic, that is, once their state and input are given, their evolution is uniquely determined.

**Definition of deterministic finite automaton**

Let Q be a finite set and let be a finite set of symbols. Also let be a function from Q to Q , let q_{0} be a state in Q and let A be a subset of Q. We call the elements of Q a **state**, the **transition function**, q_{0} the **initial state** and A the set of **accepting states**.

Then a **deterministic finite automaton** is a 5-tuple < Q , , q_{0} , , A >

**Notes on the definition**

- The set Q in the above definition is simply a set with a finite number of elements. Its elements can, however, be interpreted as a state that the system (automaton) is in. Thus in the example of vending machine, for example, the states of the machine such as “waiting for a customer to put a coin in”, “have received 5 cents” etc. are the elements of Q. “Waiting for a customer to put a coin in” can be considered the initial state of this automaton and the state in which the machine gives out a soda can can be considered the accepting state.
- The transition function is also called a
**next state function**meaning that the automaton moves into the state (q, a) if it receives the input symbol a while in state q.

Thus in the example of vending machine, if q is the initial state and a nickel is put in, then (q, a) is equal to “have received 5 cents”. - Note that is a function. Thus for
**each state**q of Q and for**each symbol**a of , (q, a) must be specified. - The accepting states are used to distinguish sequences of inputs given to the finite automaton. If the finite automaton is in an accepting state when the input ceases to come, the sequence of input symbols given to the finite automaton is “accepted”. Otherwise it is not accepted. For example, in the Example 1 below, the string a is accepted by the finite automaton. But any other strings such as aa, aaa, etc. are not accepted.
- A deterministic finite automaton is also called simply a “finite automaton”. Abbreviations such as
**FA**and**DFA**are used to denote deterministic finite automaton.

DFAs are often represented by digraphs called **(state) transition diagram**. The vertices (denoted by single circles) of a transition diagram represent the states of the DFA and the arcs labeled with an input symbol correspond to the transitions. An arc ( p , q ) from vertex p to vertex q with label represents the transition (p, ) = q . The accepting states are indicated by double circles.

Transition functions can also be represented by tables as seen below. They are called **transition table**.

**Examples of finite automaton**

**Example 1:** Q = { 0, 1, 2 }, = { a }, A = { 1 }, the initial state is 0 and is as shown in the following table.

State (q) | Input (a) | Next State ( (q, a) ) |

0 | a | 1 |

1 | a | 2 |

2 | a | 2 |

A state transition diagram for this DFA is given below.

If the alphabet of the Example 1 is changed to { a, b } in stead of { a }, then we need a DFA such as shown in the following examle to accept the same string a. It is a little more complex DFA.

**Example 2:** Q = { 0, 1, 2 }, = { a, b }, A = { 1 }, the initial state is 0 and is as shown in the following table.

State (q) | Input (a) | Next State ( (q, a) ) |

0 | a | 1 |

0 | b | 2 |

1 | a | 2 |

1 | b | 2 |

2 | a | 2 |

2 | b | 2 |

Note that for each state there are two rows in the table for corresponding to the symbols a and b, while in the Example 1 there is only one row for each state.

A state transition diagram for this DFA is given below.

A DFA that accepts all strings consisting of only symbol a over the alphabet { a, b } is the next example.

**Example 3:** Q = { 0, 1 }, = { a, b }, A = { 0 }, the initial state is 0 and is as shown in the following table.

State (q) | Input (a) | Next State ( (q, a) ) |

0 | a | 0 |

0 | b | 1 |

1 | a | 1 |

1 | b | 1 |

A state transition diagram for this DFA is given below.

**Example 4:** For the example of vending machine of the previous section, Q = { 0, 5, 10, 15, 20 }, = { D, N }, A = { 15, 20 }, the initial state q_{0} = 0. If we make it a DFA, its transition function is as shown in the following table.

State (q) | Input (a) | Next State ( (q, a) ) |

0 | N | 5 |

0 | D | 10 |

5 | N | 10 |

5 | D | 15 |

10 | N | 15 |

10 | D | 20 |

15 | N | 5 |

15 | D | 10 |

20 | N | 5 |

20 | D | 10 |

**A finite automaton as a machine**

A finite automaton can also be thought of as the device shown below consisting of a tape and a control circuit which satisfy the following conditions:

- The tape has the left end and extends to the right without an end.
- The tape is divide into squares in each of which a symbol can be written prior to the start of the operation of the automaton.
- The tape has a read only head.<p; =”” r=””>
- The head is always at the leftmost square at the beginning of the operation.
- The head moves to the right one square every time it reads a symbol.

It never moves to the left. When it sees no symbol, it stops and the automaton terminates its operation. - There is a finite control which determines the state of the automaton and also controls the movement of the head.

**Operation of finite automata**

Let us see how an automaton operates when it is given some inputs. As an example let us consider the DFA of Example 3 above.

Initially it is in state 0. When zero or more a’s are given as an input to it, it stays in state 0 while it reads all the a’s (without breaks) on the tape. Since the state 0 is also the accepting state, when all the a’s on the tape are read, the DFA is in the accepting state. Thus this automaton accepts any string of a’s. If b is read while it is in state 0 (initially or after reading some a’s), it moves to state 1. Once it gets to state 1, then no matter what symbol is read, this DFA never leaves state 1. Hence when b appears anywhere in the input, it goes into state 1 and the input string is not accepted by the DFA. For example strings aaa, aaaaaa etc. are accepted but strings such as aaba, b etc. are not accepted by this automaton.

**EXAMPLE 1**

# 0and1Even

This automaton recognizes:

- the empty string;
- the set of strings with an even number of
`1`

‘s and an even number of`0`

‘s;

**EXAMPLE 2**

# a(bb)*bc

This automaton recognizes:

the language `a(bb)*bc`

, i. e. the language formed by words that begin with an `a`

followed by an odd number of `b`

and a final `c`

.

**EXAMPLE 3**

# Binary Odd Numbers

This automaton recognizes:

binary odd numbers.

**EXAMPLE 4**

# 00(1|0)*11

This automaton recognizes:

sequences of digits that begin at least with two 0 and finish with at least two 1, i. e. the language.

**EXAMPLE 5**

# Even number of b’s

This automaton recognizes:

the set of all strings over the alphabet `{a,b}`

that have an even number of `b`

‘s.

**EXAMPLE 6**

# At Most Two Consecutive b

** This automaton recognizes:**

any sequence on the alphabet `I={a,b}`

containing at most two consecutive `b`

‘s.

**Problems on Deterministic Finite State Automata**

Problem 1:

Let

Mbe a deterministic FSA. Under exactly what circumstances ise є L(M)?( 2.1.1. p.60)

Answer: Problem 2:e є L(M) iff the starting state is a final state, i.e. s є F.

Describe informally the language accepted by the following FSAs:

(initial states are represented as: Final states are represented as:

a. Problem 3The language is represented by the regular expression

a(ba)*

b.

The language is represented by the regular expression

a*b

Construct a deterministic FSA accepting each of the following languages (an FSA per language):

- {w
є {a,b}*:eachainis immediately preceded bywb} solution- {w
є {a,b}*:haswababas a substring} solution- {w
є {a,b}*:has neitherwaanorbbas a substring} solution- {w
є {a,b}*:has an odd number ofwa‘s and an even number ofb‘s} solution- {w
є {a,b}*:has bothwabandbaas substrings}solutionThe basic technique to construct an FSA:

Think of the minimal instance of a string satisfying the conditions of the problem, and build incompletely defined FSA that accepts that string. Then make the FSA complete by adding the necessary transitions.Solutions:Problem 3(a)

{w є {a,b}*:eachainis immediately preceded bywb}The alphabet would be: {a,b} Let q0 be the initial state. We want each

ato be preceded byb, so the first symbol to be accepted should beb(i.e. the strings should start withb)There may be only one

b, so q1 should be a final state.Before the first

ato come there may be any number ofb‘s, accepted while the FSA is in state q1:We are ready to accept

anow. This may be the last symbol, so fromq1onathe FSA may go to a final state, or may continue to acceptb‘sThus we make a link from q1 to q0, and adding q0 to the set of final states:

The FSA built so far accepts strings where each

ais preceded bybHowever, the FSA is not completely defined.

So far we have:

δ(q0,a) = ?

δ(q0,b) = q1

δ(q1,a) = q0

δ(q1,b) = q1If at q0 the input is

a,the string should not be accepted. The technique here is:Add another state, q2, not final Thus if the string contains two or more consecutive

Addδ(q0,a) = q2

δ(q2,a) = q2

δ(q2,b) = q2a’s the FSA will wind up inq2and will stay there till the end of the string. Sinceq2is not a final state, the string would not be accepted.The final FSA is:

Formally, the FSA is represented by:

K = {q0,q1,q2} Problem 3(b)

∑ = {a,b}

s = q0

F = {q1}Transition function given by the following table:

a b ------------------- q0 q2 q1 q1 q0 q1 q2 q2 q2

{w є {a,b}*:haswababas a substring}We first build an incomplete FSA that accepts Problem 3(c)abab,and then we’ll make it complete.The initial state will be q0, the final state – q4

Now we have to completely define the transition function.

- What happens if at q0 we get
b‘s? We just stay there waiting for ana.- What happens if at q1 we get one or more
a‘s? We stay there waiting forbto come.- What happens if at q2 we get
b?The FSA has readab.Anotherbwill spoil thesubstring (abab),so we have to start where we wait for ana,i.e. at q0.- What happens if at q3 we get
a?We have read so faraba, and wait forb.Anawill spoil the substring, but it can be considered as the firstaof another substring“abab”,so we have to go where the firstbis waited: at q1.- At q4 we are sure that the string contains
abab, so any sequence ofa‘s andb‘s is allowed.Thus the FSA will be:

Formally, the FSA is represented by:

K = {q0,q1,q2, q3,q4}

∑ = {a,b}

s = q0

F = {q4}Transition function given by the following table:

a b ------------------ q0 q1 q0 q1 q1 q2 q2 q3 q0 q3 q4 q1 q4 q4 q4

{w є {a,b}*:has neitherwaanorbbas a substring}Here we don’t want Problem 3(d)aaorbb,so we’ll have one path foraaand one path forbbwinding up in a state that is not final and staying there till the end of the string.The states q1 and q2 are guards: if at q1 a second

acomes, the FSA gets into q3, if at q2 a secondbcomes, the FSA again gets into q3, and once at q3, theer is no way out – q3 is designed not to be a final state.Now we have constructed an FSA that rejects any string starting with

aa, orbb.We still have not defined the set of final states, and the transition function for (q1,b) and(q2,a).

If the string is empty, If at q1 the input isaaandbbwould not be there, so the empty string is acceptable, hence q0 has to be a final state.If the string has only one

a, or only oneb, it is acceptable, so q1 and q2 have to be final states too.Thus F = {q0,q1,q2}

b, the FSA has to pass to q2 – this is the state that guards theb‘s. If at q2 we have ana, the FSA has to pass to q1 – this is the state that guards thea’s. As long as the input isababababa… orbababababa… the FSA moves between q1 and q2 and can stop at either of them – the string is acceptable. If however at q1 we get ana,it would be preceded by anothera,and then the string is not acceptable – that is why we end up in q3 and stay there no matter what comes next. Same is true if at q2 we get ab.Thus we have:

K = {q0,q1,q2,q3}

∑ = {a,b}

s = q0

F = {q0,q1,q2}The transition function is given in the following table.

a b ------------------ q0 q1 q2 q1 q3 q2 q2 q1 q3 q3 q3 q3{w

є {a,b}*:has an odd number ofwa‘s and an even number ofb‘s}The state diagram of this FSA is as follows: Problem 3(e)The initial state is q0, and the final state is q1.

Let us see how this diagram has been constructed.

Consider the paths from q0 to q1 without loops (cycles).If you go to the right, (q0,q1) this path has odd number of

a‘s (exactly onea)And even number of

b‘s (zerob‘s)If you go to the left (q0,q2,q3,q1) this path has odd number of

a’s (q2,q3) and even number ofb‘s ((q0,q2) and (q3,q1)).If you go back and forth, you will make cycles, and each cycle in this diagram gives even number of

a‘s and even number ofb‘s. You know that when an even number is added to an odd number the result is an odd number. Also, when an even number is added to an even number, the result is an even number.Thus this FSA recognizes strings than have odd number of

a‘s and even number ofb‘s.Thus we have:

K = {q0,q1,q2,q3}

∑ = {a,b}

s = q0

F = {q1}The transition function is given in the following table.

a b ------------------- q0 q1 q2 q1 q0 q3 q2 q3 q0 q3 q2 q1{w

є {a,b}*:has bothwabandbaas substrings}The minimal strings that contain abandbaas substrings are: abaandbab.So we need one path of three links, corresponding to

aba, and one path of three links corresponding tobab.Both will start at the initial state, and will end at some final state, probably the same for the two paths.The FSA that accepts

abaandbabis the following:This FSA is still not completed. We have to see what would be the transition at q1 and q5 on

a, at q2 and q4 onb, and at q3 onaandb.If we are at q1 or q5 and another Thus we arrive at the following diagram:acomes, we just stay there waiting forbto come. In any casebwill be preceded by ana, so we will not miss the substringab.If we are at q2 or q4 and a

bcomes, we stay there waiting for theato come. In any caseawill be preceded by ab,so the substringbawill be there.At q3 we have already the necessary substrings, so we accept anything that follows.

Thus we have:

K = {q0,q1,q2,q3, q4, q5}

∑ = {a,b}

s = q0

F = {q3}The transition function is given in the following table.

a b ------------------- q0 q1 q4 q1 q1 q2 q2 q3 q2 q3 q3 q3 q4 q5 q4 q5 q5 q3