Finite Automata

• Deterministic Finite Automaton (DFA)

• Non-Deterministic Finite Automaton (NFA)
• Equivalence of DFA and NFA

CMPE 322/327 Theory of Computation 1

Deterministic Finite Automaton (DFA)

CMPE 322/327 Theory of Computation 2

 Deterministic Finite Automaton (DFA)
A Deterministic Finite Automaton (DFA) is a quintuple
A = (Q, , , q0, F)

1. Q is a finite set of states

2. is a finite set of symbols (alphabet)
3. Delta ( ) is a transition function (q,a) p
4. q0 is the start state (q 0 Q)
5. F is a set of final (accepting) states ( F Q)

• Transition function takes two arguments: a state and an input symbol.

• (q, a) = the state that the DFA goes to when it is in state q and input a is received.

CMPE 322/327 Theory of Computation 3

 Graph Representation of DFA
• Nodes = states.

• Arcs represent transition function.

– Arc from state p to state q labeled by all those input symbols that have transitions
from p to q.

• Arrow labeled “Start” to the start state.

• Final states indicated by double circles.

CMPE 322/327 Theory of Computation 4

 Graph Representation of a DFA: Example
A DFA: Accepts all strings without two consecutive 1’s.

0 0,1
1 1
A B C

start 0

DFA = (Q, , , q0, F)

– Q = {A,B,C} = {0,1} q0 = A F = {A,B}
• States:
– State A: previous string is OKAY, and it does not end in 1.
– State B: previous string is OKAY, and it ends in 1.
– State C: previous string contains two consecutive 1’s (it is NOT OKAY).

CMPE 322/327 Theory of Computation 5

 Alternative Representation:
Transition Table

Columns = input symbols

Final states starred

0 1
Arrow for * A A B
start state * B A C
C C C

Rows = states

CMPE 322/327 Theory of Computation 6

 Strings Accepted by a DFA
• An DFA accepts a string w = a 1a 2... a n if its path in the transition diagram that
1. Begins at the start state
2. Ends at an accepting state

• This DFA accepts input: 010001

• This DFA rejects input: 011001

• This DFA accepts input: 0000

CMPE 322/327 Theory of Computation 7

 ෡
Extended Delta Function – Delta Hat 훅
• The transition function can be extended to extended delta function 훅෡ that operates
on states and strings (as opposed to states and symbols).

෡ can be defined induction on length of string.

• Extended delta function 훅

Basis: when the string is the empty string

Induction: when the string is a non-empty string xa

where a is an input symbol and x is a string

CMPE 322/327 Theory of Computation 8

 ෡
• Computing 훅(A,0100)
෡ for all prefixes of 0100
– Computes 훅

෠
• Since δ(A,0100)=A and A is a final state, the string 0100 is accepted by this DFA.

CMPE 322/327 Theory of Computation 9

 Language Accepted by a DFA
• Informally, the language accepted by a DFA A is the set of all strings that are
recognized by A.

• Formally, the language accepted by a DFA A is L(A) such that

L(A) = { w | 훅෡ (q ,w) F } where q is the starting state of A and
0 0
F is the final states of A

• Languages accepted by DFAs are called as regular languages.

– Every DFA accepts a regular language, and
– For every regular language there is a DFA that accepts it

CMPE 322/327 Theory of Computation 10

 Language Accepted by a DFA

0 0,1
1 1
A B C

start 0

• This DFA accepts all strings of 0’s and 1’s without two consecutive 1’s.
• Formally,
L(A) = { w | w is in {0,1}* and w does not have two consecutive 1’s }

CMPE 322/327 Theory of Computation 11

 DFA Examples
• A DFA accepting all strings of 0’s and 1’s containing 001.

1 0 0,1
0 0 1
A B C D

start 1

• What do states represent?

– A: empty string OR strings do not contain 001 and end in 1
– B: string 0 OR strings do not contain 001 and end in 10
– C: strings do not contain 001 and end in 00
– D: strings contain 001

CMPE 322/327 Theory of Computation 12

 DFA Examples
• A DFA accepting all strings of 0’s and 1’s which start with 0 and end in 1.

0 1
0 1
A B C

start 0

• What do states represent?

– A: empty string
– B: strings start with 0 and end in 0
– C: strings start with 0 and end in 1

CMPE 322/327 Theory of Computation 13

 DFA Examples: Missing Arcs

• State A does not have any arc with 1.

– What happens when symbol 1 comes when we are in state A?
• We assume that all missing arcs go to a death state DS, DS goes to itself for all
symbols and DS is a non-accepting state.

0 1
0 1
A B C
1 0,1
start 0
DS

CMPE 322/327 Theory of Computation 14

 DFA Examples
• A DFA accepting all and only strings with an even number of 0's and an even
number of 1's

What do states represent?

• q0: strings with an even number of 0's
and an even number of 1's
• q1: strings with an even number of 0's
and an odd number of 1's
• q2: strings with an odd number of 0's
and an even number of 1's
• q3: strings with an odd number of 0's
and an odd number of 1's

CMPE 322/327 Theory of Computation 15

 DFA Examples: Questions?
• Give DFA’s accepting the following languages over the alphabet {0,1}.

1. The set of all strings ending in 00.

2. The set of all strings. i.e. {0,1}*
3. The set of all non-empty strings. i.e. {0,1}+
4. The empty language. i.e. {}
5. The language that contains only the empty string. i.e. the set { }
6. The language { 0n1k | n≥1 and k≥1}
7. The strings whose second characters from the right end are 1.
8. The strings whose third characters from the right end are 1.

CMPE 322/327 Theory of Computation 16

 DFA Examples: Questions?
Language over alphabet {0,1}: The set of all strings ending in 00

CMPE 322/327 Theory of Computation 17

 DFA Examples: Questions?
Language over alphabet {0,1}: The set of all strings. i.e. {0,1}*

CMPE 322/327 Theory of Computation 18

 DFA Examples: Questions?
Language over alphabet {0,1}: The set of all non-empty strings. i.e. {0,1}+

CMPE 322/327 Theory of Computation 19

 DFA Examples: Questions?
Languages over alphabet {0,1}

The empty language. i.e. {} The language that contains only

the empty string. i.e. the set { }

with DS drawn

CMPE 322/327 Theory of Computation 20

 DFA Examples: Questions?
Language over alphabet {0,1}: The language { 0n1k | n≥1 and k≥1}

with DS drawn

CMPE 322/327 Theory of Computation 21

 DFA Examples: Questions?
• Give DFA’s accepting the following languages over the alphabet {0,1}.

The strings whose second characters from the right end are 1.

CMPE 322/327 Theory of Computation 22

 DFA Examples: Questions?
• Give DFA’s accepting the following languages over the alphabet {0,1}.

The strings whose third characters from the right end are 1.

CMPE 322/327 Theory of Computation 23

 Proofs of Set Equivalence
• We need to prove that two descriptions of sets are in fact the same set. We want to
prove that the language of a DFA is equal to a given set.

• Example:
– One set is the language of our example DFA
– The other one is “the set of strings of 0’s and 1’s with no consecutive 1’s”
• In general, we want to prove sets S and T are equal (i.e. S=T).
• In order to prove S=T, we need to prove two parts:
1. S ⊆ T i.e. If w is in S, then w is in T.
2. T ⊆ S i.e. If w is in T, then w is in S.
• Example:
– S = the language of our example DFA
– T = “the set of strings of 0’s and 1’s with no consecutive 1’s”

CMPE 322/327 Theory of Computation 24

 Proofs of Set Equivalence
Proof Part 1 : S ⊆ T
• To prove: If w is accepted by our DFA
then w has no consecutive 1’s.

• The proof is an induction of length of w.

• Important trick: Expand the inductive hypothesis to be more detailed than we need.

Inductive Hypothesis:
෡
1. If 훅(A, w) = A, then w has no consecutive 1’s and does not end in 1.
෡
2. If 훅(A, w) = B, then w has no consecutive 1’s and ends in a single 1.

CMPE 322/327 Theory of Computation 25

Proof Part 1 : S ⊆ T

Basis: |w| = 0; i.e., w = . ෠

δ(A, w) = A

• IH (1) holds since has no 1’s at all.

• IH (2) holds vacuously, since δ෠ (A, ε) is not B.

Important concept:
If the “if” part of “if..then” is false,
its conclusion is true.

CMPE 322/327 Theory of Computation 26

Proof Part 1 : S ⊆ T
Inductive Step
• Need to prove IH (1) and IH (2) for w = xa.
෠
Proof of IH (1): If δ(A,w)=A, then w has no consecutive 1’s and does not end in 1.
෠
• Since δ(A,w)=A, ෠
δ(A,x) must be A or B, and a must be 0 (look at the DFA).
• By the IH, x has no 11’s.
• Thus, w has no 11’s and does not end in 1.

෠
Proof of IH (2): If δ(A,w)=B, then w has no consecutive 1’s and ends in a single 1.
෠
• Since δ(A,w)=B, ෠
δ(A,x) must be A, and a must be 1 (look at the DFA).
• By the IH, x has no 11’s and does not end in 1.
• Thus, w has no 11’s and ends in a single 1.

CMPE 322/327 Theory of Computation 27

Proof Part 2 : T⊆S

• To prove: If w has no 11’s,

then w is accepted by our DFA.

• The proof is created using contrapositive.

• The contrapositive of “If w has no 11’s, then w is accepted by our DFA” is

“If w is not accepted by our DFA then w has 11”.

• In general, the contrapositive of “if X then Y” is the equivalent statement

“if not Y then not X.”

CMPE 322/327 Theory of Computation 28

Proof Part 2 : T ⊆ S

Using Contrapositive
• Every w gets the DFA to exactly one state.
– Simple inductive proof based on:
• Every state has exactly one transition on 1, one transition on 0.
• The only way w is not accepted is if it gets to C.
෠
• The only way to get to C [ formally: δ(A,w)=C ] is if w=x1y, x gets to B,
and y is the tail of w that follows what gets to C for the first time.
෠
• If δ(A,x)=B then surely x=z1 for some z.

• Thus, w = z11y and w has 11.

• By contrapositive,
If w has no 11’s, then w is accepted by our DFA.

CMPE 322/327 Theory of Computation 29

 Regular Languages
• A language L is regular if it is the language accepted by some DFA.
– A language is regular if it can be described by a regular expression.
• Some languages are not regular.
– If a language is not regular, there is no DFA for that language.

Example 1:
• L1 = {0n1n | n ≥ 1} is not regular.
• The set of strings consisting of n 0’s followed by n 1’s, such that n is at least 1.
• Thus, L1 = {01, 0011, 000111,…}

Example 2:
• L2 = {w | w in {(, )}* and w is balanced }
– Balanced parentheses are those that can appear in an arithmetic expression.
• E.g.: (), ()(), (()), (()()),…

CMPE 322/327 Theory of Computation 30

 DFA and Regular Languages
• Every DFA recognizes a regular language, and there is a DFA for every regular
language.

DFA Regular Languages

• Some languages are not regular. If a language is not regular, there is no DFA for
that language.

CMPE 322/327 Theory of Computation 31