DFA NOTES


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 q0 be a state in Q and let A be a subset of Q. We call the elements of Q a state, the transition function, q0 the initial state and A the set of accepting states.
Then a deterministic finite automaton is a 5-tuple < Q , , q0 , , A >

Notes on the definition

  1. 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.
  2. 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”.
  3. Note that is a function. Thus for each state q of Q and for each symbol a of ,   (q, a) must be specified.
  4. 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.
  5. 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 q0 = 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:

  1. The tape has the left end and extends to the right without an end.
  2. 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.
  3. The tape has a read only head.<p;  =”” r=””>
  4. The head is always at the leftmost square at the beginning of the operation.
  5. 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.
  6. 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 M be a deterministic FSA. Under exactly what circumstances is e є L(M)?

( 2.1.1. p.60)

Answer:

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

Problem 2:

Describe informally the language accepted by the following FSAs:

(initial states are represented as:

Final states are represented as:

a.

The language is represented by the regular expression a(ba)*

 

b.

 

The language is represented by the regular expression a*b

 

Problem 3

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

  1. {w є {a,b}*: each a in w is immediately preceded by b} solution
  2. {w є {a,b}*: w has abab as a substring} solution
  3. {w є {a,b}*: w has neither aa nor bb as a substring} solution
  4. {w є {a,b}*: w has an odd number of a‘s and an even number of b‘s } solution
  5. {w є {a,b}*: w has both ab and ba as substrings} solution

The 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}*: each a in w is immediately preceded by b}

The alphabet would be: {a,b}

Let q0 be the initial state. We want each a to be preceded by b, so the first symbol to be accepted should be b(i.e. the strings should start with b)

There may be only one b, so q1 should be a final state.

Before the first a to come there may be any number of b‘s, accepted while the FSA is in state q1:

We are ready to accept a now. This may be the last symbol, so from q1 on a the FSA may go to a final state, or may continue to accept b‘s

Thus 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 a is preceded by b

However, the FSA is not completely defined.

So far we have:

δ(q0,a) = ?
δ
(q0,b) = q1

δ(q1,a) = q0
δ(q1,b) = q1

If at q0 the input is a, the string should not be accepted. The technique here is:

Add another state, q2, not final
Add

δ(q0,a) = q2
δ(q2,a) = q2
δ(q2,b) = q2
Thus if the string contains two or more consecutive a’s the FSA will wind up in q2 and will stay there till the end of the string. Since q2 is not a final state, the string would not be accepted.

The final FSA is:

Formally, the FSA is represented by:

K = {q0,q1,q2}
∑ = {a,b}
s = q0
F = {q1}

Transition function given by the following table:

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

Problem 3(b)

{w є {a,b}*: w has abab as a substring}

We first build an incomplete FSA that accepts 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.

  1. What happens if at q0 we get b‘s? We just stay there waiting for an a.
  2. What happens if at q1 we get one or more a‘s? We stay there waiting for b to come.
  3. What happens if at q2 we get b? The FSA has read ab. Another b will spoil the substring (abab), so we have to start where we wait for an a, i.e. at q0.
  4. What happens if at q3 we get a? We have read so far aba, and wait for b. An a will spoil the substring, but it can be considered as the first a of another substring “abab”, so we have to go where the first b is waited: at q1.
  5. At q4 we are sure that the string contains abab, so any sequence of a‘s and b‘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

Problem 3(c)

{w є {a,b}*: w has neither aa nor bb as a substring}

Here we don’t want aa or bb, so we’ll have one path for aa and one path for bb winding 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 a comes, the FSA gets into q3, if at q2 a second bcomes, 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, or bb.

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, aa and bb would 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 one b, it is acceptable, so q1 and q2 have to be final states too.

Thus F = {q0,q1,q2}

If at q1 the input is b, the FSA has to pass to q2 – this is the state that guards the b‘s. If at q2 we have ana, the FSA has to pass to q1 – this is the state that guards the a’s. As long as the input is ababababa… 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 an a, it would be preceded by another a, 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 a b.

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

Problem 3(d)

{w є {a,b}*: w has an odd number of a‘s and an even number of b‘s }

The state diagram of this FSA is as follows:

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 one a)

And even number of b‘s (zero b‘s)

If you go to the left (q0,q2,q3,q1) this path has odd number of a’s (q2,q3) and even number of b‘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 of b‘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 of b‘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

Problem 3(e)

{w є {a,b}*: w has both ab and ba as substrings}

The minimal strings that contain ab and ba as substrings are: aba and bab.

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 aba and bab is 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 on b, and at q3 on a and b.

If we are at q1 or q5 and another a comes, we just stay there waiting for b to come. In any case bwill be preceded by an a, so we will not miss the substring ab.

If we are at q2 or q4 and a b comes, we stay there waiting for the a to come. In any case a will be preceded by a b, so the substring ba will be there.

At q3 we have already the necessary substrings, so we accept anything that follows.

Thus we arrive at the following diagram:

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