CS390: Module 3

Instructor: Dr. Lusi Li

1
 Finite Automata

• Deterministic Finite Automaton (DFA)

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

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 (q0  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.

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.

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 (does not contain 11), and it does not end in 1.
– State B: previous string is OKAY (does not contain 11), and it ends in 1.
– State C: previous string contains two consecutive 1’s (it is NOT OKAY).

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

6
 Strings Accepted by a DFA
• An DFA accepts a string w = a1a2 ... an 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

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: ෡ (q,) = q
𝜹 when the string is the empty string 

෡ (q,xa) = (𝜹(q,x),
Induction: 𝜹 ෡ a) when the string is a non-empty string xa
where a is an input symbol and x is a string

8
 ෡ ∶ Example
Extended Delta Function – Delta Hat 𝜹
෡ (A, 0100)
• Computing 𝜹
෡ for all prefixes of 0100
– Computing 𝜹

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

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

෡ (q0,w)  F }
L(A) = { w | 𝜹 where q0 is the starting state of A and
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

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 }

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

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

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

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

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.

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

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

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

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

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

with DS drawn

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.

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.

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”

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. ෡ (A,w) = B, then w has no consecutive 1’s and ends in a single 1.
If 𝜹

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.

෡ (A, ε) is not B.
• IH (2) holds vacuously, since 𝜹

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

26
Proof Part 1 : S ⊆ T

Inductive Step
• Need to prove IH (1) and IH (2) for w = xa.
෡ (A,w)=A, then w has no consecutive 1’s and does not end in 1.
Proof of IH (1): If 𝜹
෡ (A,w)=A, 𝜹
• Since 𝜹 ෡ (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.

෡ (A,w)=B, then w has no consecutive 1’s and ends in a single 1.

Proof of IH (2): If 𝜹
෡ (A,w)=B, 𝜹
• Since 𝜹 ෡ (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.

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.”

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.
෡ (A,x)=B then surely x=z1 for some z.
• If 𝜹
• Thus, w = z11y and w has 11.
• By contrapositive,
If w has no 11’s, then w is accepted by our DFA.

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.: (), ()(), (()), (()()),…

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.

31