CS206 Theory of Computing IV Semester 2025–2026

Tutorial 02: 07/01/2026

Course Instructor: Pavan Kumar C Scribes: Siddharth Gautam

Note: LaTeX template courtesy of UC Berkeley EECS department.

Disclaimer: These notes have not been subjected to formal publication review.

Deterministic Finite Automaton (DFA)

Definition: A Deterministic Finite Automaton (DFA) is a 5-tuple

M = (Q, Σ, δ, q0 , F )

Components:

• Q : finite set of states

• Σ : finite input alphabet
• δ : Q × Σ → Q : transition function
• q0 ∈ Q : initial state
• F ⊆ Q : set of accepting states

Acceptance Condition: For a string w ∈ Σ∗ , w is accepted by M if

δ ∗ (q0 , w) ∈ F,

where δ ∗ is the extended transition function.

Transition Function. The transition function of a DFA is defined as:

δ :Q×Σ→Q

That is,

δ(current state, input symbol) = next state

2-1
2-2 Tutorial 02: 07/01/2026

Example 1

Construct a DFA that accepts all strings over {0, 1} having an even number of 0’s.

Transition Function
δ(q0 , 0) = q1
δ(q1 , 0) = q0
δ(q0 , 1) = q0
δ(q1 , 1) = q1

DFA Diagram

1 1
0

start q0 q1

Explanation: q0 represents even count of 0’s and is accepting.

Formal Language Definition

L = {w ∈ {0, 1}∗ | #0(w) is even}

DFA Definition

M = ({q0 , q1 }, {0, 1}, δ, q0 , {q0 })

Transition Table
State 0 1
→∗ q0 q1 q0
q1 q0 q1

Test String

Test string: 1010

Tutorial 02: 07/01/2026 2-3

δ(q0 , 1) = q0
δ(q0 , 0) = q1
δ(q1 , 1) = q1
δ(q1 , 0) = q0

Final state q0 is accepting. Hence, 1010 is accepted ✓

Example 2

Construct a DFA that accepts all strings over {a, b} having odd number of a’s.

Transition Function

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

DFA Diagram

b b
a

start q0 q1

Explanation: Odd count of a’s leads to accepting state q1 .

Formal Language Definition

L = {w ∈ {a, b}∗ | #a(w) is odd}

DFA Definition

M = ({q0 , q1 }, {a, b}, δ, q0 , {q1 })

2-4 Tutorial 02: 07/01/2026

Transition Table
State a b
→ q0 q1 q0
∗
q1 q0 q1

Test String

Test string: aba

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

Final state q0 is non-accepting. Hence, aba is rejected ×

Example 3

Construct a DFA that accepts strings over {0, 1} whose length is divisible by 3.

Transition Function
δ(qi , 0) = q(i+1) mod 3
δ(qi , 1) = q(i+1) mod 3

DFA Diagram

0,1 0,1
start q0 q1 q2

0,1

Explanation: States represent length modulo 3.

Formal Language Definition

L = {w ∈ {0, 1}∗ | |w| ≡ 0 (mod 3)}

Tutorial 02: 07/01/2026 2-5

DFA Definition

M = ({q0 , q1 , q2 }, {0, 1}, δ, q0 , {q0 })

Transition Table

State 0 1
→∗ q0 q1 q1
q1 q2 q2
q2 q0 q0

Test String

Test string: 110

δ(q0 , 1) = q1
δ(q1 , 1) = q2
δ(q2 , 0) = q0

Final state q0 is accepting. Hence, 110 is accepted ✓

Example 4

Construct a DFA that accepts strings over {a, b} ending with ab.

Transition Function

δ(q0 , a) = q1
δ(q1 , b) = q2
δ(q2 , a) = q1
δ(q2 , b) = q0
2-6 Tutorial 02: 07/01/2026

DFA Diagram

q0 a q1 b q2
start
a
b
b

Explanation: The DFA remembers the last two symbols.

Formal Language Definition

L = {w ∈ {a, b}∗ | w ends with ab}

DFA Definition

M = ({q0 , q1 , q2 }, {a, b}, δ, q0 , {q2 })

Transition Table

State a b
→ q0 q1 q0
q1 q1 q2
∗
q2 q1 q0

Test String

Test string: aab

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

Final state q2 is accepting. Hence, aab is accepted ✓

Tutorial 02: 07/01/2026 2-7

Example 5

Construct a DFA that accepts strings containing substring 01.

DFA Diagram
1 0 0,1

q0 0 q1 1 q2
start

Explanation: Once substring 01 appears, DFA stays accepting.

Formal Language Definition

L = {w ∈ {0, 1}∗ | w contains 01}

DFA Definition

M = ({q0 , q1 , q2 }, {0, 1}, δ, q0 , {q2 })

Transition Table
State 0 1
→ q0 q1 q0
q1 q1 q2
∗
q2 q2 q2

Test String

Test string: 1001

δ(q0 , 1) = q0
δ(q0 , 0) = q1
δ(q1 , 0) = q1
δ(q1 , 1) = q2

Final state q2 is accepting. Hence, 1001 is accepted ✓

2-8 Tutorial 02: 07/01/2026

Example 6

Construct a DFA accepting strings starting with 10.

DFA Diagram

0,1

q0 1 q1 0 q2
start

0
1

qd

0,1

Explanation: Mismatch leads to dead state.

Formal Language Definition

L = {w ∈ {0, 1}∗ | w starts with 10}

DFA Definition

M = ({q0 , q1 , q2 , qd }, {0, 1}, δ, q0 , {q2 })

Transition Table
State 0 1
→ q0 qd q1
q1 q2 qd
∗
q2 q2 q2
qd qd qd

Test String

Test string: 1011

Tutorial 02: 07/01/2026 2-9

δ(q0 , 1) = q1
δ(q1 , 0) = q2
δ(q2 , 1) = q2
δ(q2 , 1) = q2

Final state q2 is accepting. Hence, 1011 is accepted ✓

Example 7

Construct a DFA that accepts strings of odd length over {a, b}.

DFA Diagram

a,b

start q0 q1

a,b

Explanation: Each symbol toggles parity of length.

Example 8

Construct a DFA accepting strings having exactly two 1’s.

DFA Diagram

q0 1 q1 1 q2 1 qd
start

0 0 0 0,1

Explanation: States count number of 1’s.

Formal Language Definition

L = {w ∈ {0, 1}∗ | #1(w) = 2}

2-10 Tutorial 02: 07/01/2026

DFA Definition

M = ({q0 , q1 , q2 , qd }, {0, 1}, δ, q0 , {q2 })

Transition Table
State 0 1
→ q0 q0 q1
q1 q1 q2
∗
q2 q2 qd
qd qd qd

Test String

Test string: 1010

δ(q0 , 1) = q1
δ(q1 , 0) = q1
δ(q1 , 1) = q2
δ(q2 , 0) = q2

Final state q2 is accepting. Hence, 1010 is accepted ✓

Example 9

Construct a DFA accepting strings ending with 01.

DFA Diagram

q0 0 q1 1 q2
start

0
0
1

Explanation: The DFA tracks the last two symbols.

Tutorial 02: 07/01/2026 2-11

Formal Language Definition

L = {w ∈ {0, 1}∗ | w ends with 01}

DFA Definition

M = ({q0 , q1 , q2 }, {0, 1}, δ, q0 , {q2 })

Transition Table
State 0 1
→ q0 q1 q0
q1 q1 q2
∗
q2 q1 q0

Test String

Test string: 1101

δ(q0 , 1) = q0
δ(q0 , 1) = q0
δ(q0 , 0) = q1
δ(q1 , 1) = q2

Final state q2 is accepting. Hence, 1101 is accepted ✓

2-12 Tutorial 02: 07/01/2026

Example 10

Construct a DFA that accepts strings starting with 01 and having even length.

L = {01, 0100, 0111, . . . }

DFA Diagram

0,1
0 1
start q0 q1 q2 q3

0,1
1 0

q4

0,1

Formal Language Definition

L = {w ∈ {0, 1}∗ | w starts with 01 and |w| is even}

Transition Table
State 0 1
→ q0 q1 q4
q1 q4 q2
∗
q2 q3 q3
Test String q3 q2 q2
q4 q4 q4
Test string: 0101

δ(q0 , 0) = q1
δ(q1 , 1) = q2
δ(q2 , 0) = q3
δ(q3 , 1) = q2

Final state q2 is accepting. Hence, 0101 is accepted ✓

Tutorial 02: 07/01/2026 2-13

Example 11

Construct DFA that accepts strings having:

• odd number of a’s

• even number of b’s

Σ = {a, b}, |w| ≥ 2

DFA Structure

States represent parity of a’s and b’s.

b
start q0
b
q1

a a a a

q2 b q3

b
a a

Similarly, DFA design is used for strings having:

• even a’s and odd b’s ⇒ q1 as final state

• even a’s and even b’s ⇒ q0 as final state
• odd a’s and odd b’s ⇒ q3 as final state
• odd a’s and even b’s ⇒ q2 as final state

Only the final state changes for other parity combinations

2-14 Tutorial 02: 07/01/2026

Formal Language Definition

L = {w ∈ {a, b}∗ | #a(w) is odd and #b(w) is even}

DFA Definition

M = (Q, Σ, δ, q0 , F )

where,
Q = {q0 , q1 , q2 , q3 }, Σ = {a, b}, q0 is the start state
F = {q2 }

DFA State Description

• q0 : Even number of a’s and even number of b’s
• q1 : Even number of a’s and odd number of b’s
• q2 : Odd number of a’s and even number of b’s (accepting)
• q3 : Odd number of a’s and odd number of b’s

Transition Table
State a b
→ q0 q2 q1
q1 q3 q0
∗
q2 q0 q3
q3 q1 q2

Test String

Test string: aba

δ(q0 , a) = q2 (odd a, even b)

δ(q2 , b) = q3 (odd a, odd b)
δ(q3 , a) = q1 (even a, odd b)

Final state reached is q1 , which is not accepting. Hence, aba is rejected ×