PadhaikoAll subjects

Finite State Machines & DFA Design

Theory of Computation (ENCT 203)

Open in the Padhaiko app

2.1 Introduction to Finite Automata

Definition

Finite Automaton (Finite-State Machine)

A finite automaton (also called a finite-state machine (FSM) or finite-state automaton (FSA); plural: automata) is a mathematical model of computation representing an abstract machine that can be in exactly one of a finite number of internal states at any given time.

Applications of Finite Automata

Finite automata model hardware and software systems with a strictly bounded amount of memory:

  1. Embedded & Digital Controllers: Automatic door controllers, elevator controllers, household appliance controllers (dishwashers, electronic thermostats), and control units inside digital watches and calculators.
  2. Compiler Design (Lexical Analysis): The lexical analyzer (scanner) of a compiler simulates finite automata to tokenize identifiers, keywords, operators, and numeric literals.
  3. Pattern Matching & Text Search: Efficient algorithms for locating occurrences of a pattern string inside a larger text body (such as web-page indexing or network packet inspection) are built directly from finite automata.

Block Diagram of a Finite Automaton

A finite automaton consists of three physical/conceptual components working together:

Input tape:   | a | b | a | b | a | b |
                        ^
                        |
                   Reading head
                  +------------+
                  |     q0     |
                  | q3 ----> q1|
                  |     q2     |
                  +------------+
                  Finite control
  1. Input Tape: Divided into discrete cells, each holding a single symbol from the input alphabet . The input string is placed on the tape and is read-only (the automaton cannot rewrite the tape).
  2. Reading Head: Scans one tape cell at a time, moving strictly from left to right one cell per step.
  3. Finite Control: Maintains the current internal state and consults the transition rules to move to the next state based on the current state and the symbol under the reading head.

Physical Example: Automatic Door Controller

Consider an automatic office doorway controller with one bit of memory representing two states: Closed and Open. Sensors at the doorway detect four possible input conditions:

If the door is Closed and senses F, it transitions to Open; if it senses R, B, or N while Closed, it stays Closed. Once Open, it remains Open as long as someone is present (F, R, or B) so the door does not close on a person passing through, and returns to Closed only when N is sensed.

Current StateN (Neither)F (Front)R (Rear)B (Both)
ClosedClosedOpenClosedClosed
OpenClosedOpenOpenOpen

Modelling Closed as the start state and Open as the active/accepting state over gives the state diagram below:

Physical Example: Automatic Door ControllerDFA
Physical Example: Automatic Door Controller F, R, B R, B, N F N Closed Open
StateRBNF
→ClosedClosedClosedClosedOpen
*OpenOpenOpenClosedOpen

Mathematical Example: Processing a String on Automaton

Consider the finite automaton with states , start state (marked by an incoming arrow), and final state (marked by a double circle):

Mathematical Example: Processing a String on AutomatonDFA
Mathematical Example: Processing a String on Automaton 1 0 1 0 0, 1 q1 q2 q3
State01
→q1q1q2
*q2q3q2
q3q2q2

When is given the input string , computation proceeds left-to-right from the start state :


2.2 Deterministic Finite Automata (DFA) (Book 2.2.1)

Definition

Deterministic Finite Automaton (DFA)

A Deterministic Finite Automaton (DFA) is a finite automaton in which the next state is uniquely determined by the current state and the input symbol currently being read. For every state and every input symbol , there is exactly one outgoing transition labeled , and there are no -moves.

Formally, a DFA is a 5-tuple (quintuple)

where:

For instance, the following two-state DFA over uniquely predicts the next state for every input and accepts all strings containing at least one b:

2.2.1 Deterministic Finite Automata (DFA)DFA
2.2.1 Deterministic Finite Automata (DFA) a, b a b q0 q1
Stateab
→q0q0q1
*q1q1q1
Definition

Configuration and Yield Relation of a DFA

Let be a DFA.


Worked Out Examples (Book Examples 2.1–2.6)

Example 2.1

DFA for Strings with an Even Number of b's

Design a deterministic finite automaton that accepts the language

Define the states and 5-tuple

Track the parity of the number of 's read so far using two states:

  • : the number of 's read so far is even (including , so is both the start state and the accepting state).
  • : the number of 's read so far is odd.

Thus where , , , and .

Construct the transition table and state diagram

Reading a does not change the count of 's, whereas reading b toggles the parity between and :

State
Worked Out Example 2.1 — DFA for Strings with an Even Number of b'sDFA
Worked Out Example 2.1 — DFA for Strings with an Even Number of b's a a b b q0 q1
Stateab
→*q0q0q1
q1q1q0
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts a
  • ✓ accepts bb
  • ✓ accepts bab
  • ✓ accepts ababa
  • ✓ rejects b
  • ✓ rejects ab
  • ✓ rejects bbb
  • ✓ rejects babb
Trace on test string bab
Answer:

with , , , and .

Example 2.2

DFA for Strings Not Containing Three Consecutive b's

Design a DFA that accepts the language

Define the states and 5-tuple

Count how many consecutive 's occur at the end of the prefix read so far:

  • : the prefix does not contain bbb and currently ends with consecutive 's (either empty or ending in a).
  • : the prefix does not contain bbb and ends with exactly one b.
  • : the prefix does not contain bbb and ends with bb (two consecutive 's).
  • : trap (dead) state reached as soon as bbb is encountered.

Whenever a is read in or , the run of consecutive 's resets to . Thus

Construct the transition table and state diagram
State
Worked Out Example 2.2 — DFA for Strings Not Containing Three Consecutive b'sDFA
Worked Out Example 2.2 — DFA for Strings Not Containing Three Consecutive b's a, b a b b a b a q0 q1 q2 q3
Stateab
→*q0q0q1
*q1q0q2
*q2q0q3
q3q3q3
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts b
  • ✓ accepts bb
  • ✓ accepts abbab
  • ✓ accepts bbabb
  • ✓ rejects bbb
  • ✓ rejects abbb
  • ✓ rejects bbba
  • ✓ rejects abbba
Trace on test string abbab and note complementation

Swapping accepting and non-accepting states () yields the complementary DFA accepting :

Worked Out Example 2.2 — DFA for Strings Not Containing Three Consecutive b'sDFA
Worked Out Example 2.2 — DFA for Strings Not Containing Three Consecutive b's a, b a b b a b a q0 q1 q2 q3
Stateab
→q0q0q1
q1q0q2
q2q0q3
*q3q3q3
  • Machine-checked
  • ✓ accepts bbb
  • ✓ accepts abbb
  • ✓ accepts bbba
  • ✓ accepts abbba
  • ✓ rejects ε
  • ✓ rejects b
  • ✓ rejects bb
  • ✓ rejects abbab
  • ✓ rejects bbabb
Answer:

, where reading a in resets to , reading b advances , and is a non-accepting trap state.

Example 2.3

DFA for Strings Beginning with 01

Design a DFA that accepts the language

Define the states and 5-tuple

Let with , , , and :

  • : initial state (no symbols read yet).
  • : first symbol read was 0.
  • : prefix 01 has been matched (accepting trap state).
  • : dead (rejecting trap) state for strings starting with 1 or 00.
Construct the transition table and state diagram
State
Worked Out Example 2.3 — DFA for Strings Beginning with 01DFA
Worked Out Example 2.3 — DFA for Strings Beginning with 01 0, 1 0, 1 0 1 1 0 q0 q1 q3 q2
State01
→q0q1q3
q1q3q2
q3q3q3
*q2q2q2
  • Machine-checked
  • ✓ accepts 01
  • ✓ accepts 010
  • ✓ accepts 011
  • ✓ accepts 01110
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 1
  • ✓ rejects 00
  • ✓ rejects 10
  • ✓ rejects 11
Trace on test string 01110
Answer:

with , , for , and all other transitions entering dead state .

Example 2.4

DFA for Strings Beginning with 01 of Even Length

Design a DFA that accepts the language

Define the states and 5-tuple

Let with , , , and :

  • : start state (length , even).
  • : read 0 (length , odd).
  • : begins with 01 and current length is even (accepting state, first reached at length ).
  • : begins with 01 and current length is odd (non-accepting state).
  • : dead state (first two symbols were not 01).
Construct the transition table and state diagram

Once 01 is matched at , every subsequent symbol (0 or 1) alternates between (even length) and (odd length):

State
Worked Out Example 2.4 — DFA for Strings Beginning with 01 of Even LengthDFA
Worked Out Example 2.4 — DFA for Strings Beginning with 01 of Even Length 0, 1 0 1 1 0 0, 1 0, 1 q0 q1 q4 q2 q3
State01
→q0q1q4
q1q4q2
q4q4q4
*q2q3q3
q3q2q2
  • Machine-checked
  • ✓ accepts 01
  • ✓ accepts 0100
  • ✓ accepts 0111
  • ✓ accepts 011100
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 010
  • ✓ rejects 011
  • ✓ rejects 0011
  • ✓ rejects 1001
Trace on test string 011100
Answer:

where , states and alternate on every symbol , and is the dead state.

Example 2.5

DFA for Strings with Neither 00 Nor 11 as Substrings

Design a DFA that accepts the language

Define the states and 5-tuple

A string has neither 00 nor 11 if and only if its symbols strictly alternate (0101... or 1010...). Let , , , and :

  • : start state ( read; valid).
  • : valid string so far, last symbol read was 0.
  • : valid string so far, last symbol read was 1.
  • : dead state (reached upon reading a second consecutive 0 from or a second consecutive 1 from ).
Construct the transition table and state diagram
State
Worked Out Example 2.5 — DFA for Strings with Neither 00 Nor 11 as SubstringsDFA
Worked Out Example 2.5 — DFA for Strings with Neither 00 Nor 11 as Substrings 0, 1 0 1 0 1 0 1 q0 q1 q3 q2
State01
→*q0q1q3
*q1q2q3
*q3q1q2
q2q2q2
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts 0
  • ✓ accepts 1
  • ✓ accepts 01
  • ✓ accepts 10
  • ✓ accepts 01010
  • ✓ rejects 00
  • ✓ rejects 11
  • ✓ rejects 0110
  • ✓ rejects 010100
Trace on test string 010100
Answer:

with as the non-accepting dead state.

Example 2.6

DFA for Number of a's Multiple of 4

Design a DFA that accepts the language

Define the states and 5-tuple

Track the number of 's modulo using four states , where state () means . Since is a multiple of , and .

Construct the transition table and state diagram

Reading b leaves the remainder unchanged (), whereas reading a increments the remainder modulo ():

State
Worked Out Example 2.6 — DFA for Number of a's Multiple of 4DFA
Worked Out Example 2.6 — DFA for Number of a's Multiple of 4 b b b b a a a a q0 q1 q2 q3
Stateab
→*q0q1q0
q1q2q1
q2q3q2
q3q0q3
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts b
  • ✓ accepts aaaa
  • ✓ accepts aaaba
  • ✓ accepts baaaab
  • ✓ rejects a
  • ✓ rejects aa
  • ✓ rejects aaa
  • ✓ rejects aaaaa
Trace on test string aaaba
Answer:

with cycle and self-loops on .


Solutions to Important Questions (Questions 1–12, Book pp. 95–106)

Example

Important Question 1 — Even Number of a's and Odd Number of b's [2082 Kartik, 2075 Chaitra, 2072 Chaitra]

Design a DFA for the language

Also test your design for the string "aabbb".

Define the four parity states

Let where , , , and :

  • : (even , even ) — initial state.
  • : (even , odd ) — accepting state.
  • : (odd , even ).
  • : (odd , odd ).
Transition table and state diagram
State
Important Question 1 — Even Number of a's and Odd Number of b's [2082 Kartik, 2075 Chaitra, 2072 Chaitra]DFA
Important Question 1 — Even Number of a's and Odd Number of b's [2082 Kartik, 2075 Chaitra, 2072 Chaitra] b b a a b b a a q0 q1 q2 q3
Stateba
→q0q1q2
*q1q0q3
q2q3q0
q3q2q1
  • Machine-checked
  • ✓ accepts b
  • ✓ accepts aab
  • ✓ accepts aba
  • ✓ accepts baa
  • ✓ accepts aabbb
  • ✓ rejects ε
  • ✓ rejects a
  • ✓ rejects ab
  • ✓ rejects bb
  • ✓ rejects aa
Test for 'aabbb'
Answer:

, and "aabbb" ends in (accepted).

Example

Important Question 2 — Strings Ending in Either 00 or 11 [2082 Baishakh]

Design a DFA that reads strings over and accepts only those strings that end in either 00 or 11. Verify your design by processing and .

Define the states and transitions

Track the last one or two identical symbols seen:

  • : start state ().
  • : ends in a single 0 (not 00).
  • : ends in 00 (accepting).
  • : ends in a single 1 (not 11).
  • : ends in 11 (accepting).
State
Important Question 2 — Strings Ending in Either 00 or 11 [2082 Baishakh]DFA
Important Question 2 — Strings Ending in Either 00 or 11 [2082 Baishakh] 1 0 0 1 0 1 1 0 1 0 q0 q1 q3 q2 q4
State01
→q0q1q3
q1q2q3
q3q1q4
*q2q2q3
*q4q1q4
  • Machine-checked
  • ✓ accepts 00
  • ✓ accepts 11
  • ✓ accepts 00110111
  • ✓ accepts 01110100
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 1
  • ✓ rejects 01
  • ✓ rejects 10
  • ✓ rejects 0010
Verify on and

For :

For :

Answer:

; both 00110111 (ending in ) and 01110100 (ending in ) are accepted.

Example

Important Question 3 — Strings Not Containing Two Consecutive b's [2081 Chaitra]

Construct a DFA that accepts all strings over that do not contain two consecutive 's, and process the string .

Define the states and state diagram
  • : valid string not ending in b (accepting).
  • : valid string ending in a single b (accepting).
  • : dead state reached once bb appears (rejecting).
Important Question 3 — Strings Not Containing Two Consecutive b's [2081 Chaitra]DFA
Important Question 3 — Strings Not Containing Two Consecutive b's [2081 Chaitra] a, b a b a b q0 q1 q2
Stateab
→*q0q0q1
*q1q0q2
q2q2q2
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts a
  • ✓ accepts b
  • ✓ accepts ab
  • ✓ accepts ba
  • ✓ accepts baba
  • ✓ rejects bb
  • ✓ rejects abb
  • ✓ rejects bba
  • ✓ rejects baaababb
Process
Answer:

, and terminates in (rejected).

Example

Important Question 4 — Binary Strings Divisible by 3 [2080 Bhadra]

Construct a DFA that accepts the set of all strings over which, when interpreted as a binary number, are divisible by . Verify your design with suitable examples.

Track the remainder modulo 3

If the binary prefix read so far has value , appending bit yields the new value :

  • State (, accepting): , .
  • State (): , .
  • State (): , .
Important Question 4 — Binary Strings Divisible by 3 [2080 Bhadra]DFA
Important Question 4 — Binary Strings Divisible by 3 [2080 Bhadra] 1 0 1 0 1 0 q0 q1 q2
State01
→*q0q0q1
q1q2q0
q2q1q2
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts 0
  • ✓ accepts 11
  • ✓ accepts 110
  • ✓ accepts 1001
  • ✓ accepts 1100
  • ✓ rejects 1
  • ✓ rejects 10
  • ✓ rejects 100
  • ✓ rejects 101
  • ✓ rejects 1010
Verify on and
  • For (, divisible by ):
  • For (, not divisible by ):
Answer:

with .

Example

Important Question 5 — Strings Containing Either 'ab' or 'bba' as Substring [2080 Baishakh, 2079 Baishakh]

Design a deterministic finite automaton accepting strings over containing either ab or bba as a substring.

Define the states
  • : start state ().
  • : last symbol was a (waiting for b to complete ab).
  • : accepting trap state (either ab or bba has been seen).
  • : read a single b without any prior a (since any a followed by b would already have triggered ab).
  • : read two or more 's (bb...) without any prior a (waiting for a to complete bba).
Transition table and state diagram
State
Important Question 5 — Strings Containing Either 'ab' or 'bba' as Substring [2080 Baishakh, 2079 Baishakh]DFA
Important Question 5 — Strings Containing Either 'ab' or 'bba' as Substring [2080 Baishakh, 2079 Baishakh] b a, b a a b b a b a q0 q1 q3 q2 q4
Stateab
→q0q1q3
q1q1q2
q3q1q4
*q2q2q2
q4q2q4
  • Machine-checked
  • ✓ accepts ab
  • ✓ accepts bba
  • ✓ accepts aab
  • ✓ accepts bbba
  • ✓ accepts bab
  • ✓ rejects ε
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects ba
  • ✓ rejects bb
  • ✓ rejects baa
Answer:

.

Example

Important Question 6 — Neither '00' Nor '11' as Substring, Tested on 01011010 [2079 Bhadra, 2076 Ashwin]

Design a DFA that accepts , and test your design for 01011010.

Construct the DFA

Using the same 4-state construction as Worked Out Example 2.5 (, , , dead state ):

StateSymbol Symbol
Important Question 6 — Neither '00' Nor '11' as Substring, Tested on 01011010 [2079 Bhadra, 2076 Ashwin]DFA
Important Question 6 — Neither '00' Nor '11' as Substring, Tested on 01011010 [2079 Bhadra, 2076 Ashwin] 0, 1 0 1 1 0 0 1 q0 q1 q3 q2
State01
→*q0q1q3
*q1q2q3
*q3q1q2
q2q2q2
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts 0
  • ✓ accepts 1
  • ✓ accepts 0101
  • ✓ accepts 1010
  • ✓ rejects 00
  • ✓ rejects 11
  • ✓ rejects 01011010
Test on 01011010
Answer:

The string 01011010 enters the dead state upon reading the substring 11 and is rejected.

Example

Important Question 7 — Number of a's Divisible by 3 and Number of b's Divisible by 2 [2075 Ashwin]

Design a DFA that accepts the language

Define the 6 product states

Track using states :

  • (start and only accepting state), , (even number of 's).
  • , , (odd number of 's).
Transition table and state diagram

Reading a cycles and ; reading b swaps , , and :

StateSymbol Symbol
Important Question 7 — Number of a's Divisible by 3 and Number of b's Divisible by 2 [2075 Ashwin]DFA
Important Question 7 — Number of a's Divisible by 3 and Number of b's Divisible by 2 [2075 Ashwin] a b a b a b a b a b a b q0 q1 q3 q2 q4 q5
Stateab
→*q0q1q3
q1q2q4
q3q4q0
q2q0q5
q4q5q1
q5q3q2
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts aaa
  • ✓ accepts bb
  • ✓ accepts aaabb
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects aa
  • ✓ rejects ab
  • ✓ rejects aaab
  • ✓ rejects ababab
Test on 'aaabb'
Answer:

.

Example

Important Question 8 — Strings Starting with 01 or Ending with 01 [2074 Ashwin]

Design a DFA that accepts strings over that either start with 01 or end with 01. Test your design on two strings.

Define the 6 states

Let , , , and :

  • : start state ().
  • : first symbol is 0.
  • : string started with 01 (accepting trap state).
  • : string did not start with 01 and currently ends in 1.
  • : string did not start with 01 and currently ends in 0.
  • : string did not start with 01 and currently ends in 01 (accepting state).
Transition table and state diagram
StateSymbol Symbol
Important Question 8 — Strings Starting with 01 or Ending with 01 [2074 Ashwin]DFA
Important Question 8 — Strings Starting with 01 or Ending with 01 [2074 Ashwin] 0 1 0, 1 0 1 1 0 0 1 0 1 q0 q1 q3 q2 q4 q5
State01
→q0q1q3
q1q4q2
q3q4q3
*q2q2q2
q4q4q5
*q5q4q3
  • Machine-checked
  • ✓ accepts 01
  • ✓ accepts 01110
  • ✓ accepts 1001
  • ✓ accepts 0001
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 1
  • ✓ rejects 10
  • ✓ rejects 0010
  • ✓ rejects 1100
Test on '01110' and '1001'
  • For "01110" (starts with 01):
  • For "1001" (ends with 01):
Answer:

.

Example

Important Question 9 — Strings Having Either 'aa' or 'bb' as a Substring [2074 Chaitra]

Design a DFA that accepts the language

Define the 5 states

Let , , , and :

  • : start state ().
  • : no aa/bb yet; last symbol was a.
  • : aa has been seen (accepting trap state).
  • : no aa/bb yet; last symbol was b.
  • : bb has been seen (accepting trap state).
Transition table and state diagram
State ()Symbol Symbol
Important Question 9 — Strings Having Either 'aa' or 'bb' as a Substring [2074 Chaitra]DFA
Important Question 9 — Strings Having Either 'aa' or 'bb' as a Substring [2074 Chaitra] a, b a, b a b a b a b q0 q1 q3 q2 q4
Stateab
→q0q1q3
q1q2q3
q3q1q4
*q2q2q2
*q4q4q4
  • Machine-checked
  • ✓ accepts aa
  • ✓ accepts bb
  • ✓ accepts aabab
  • ✓ accepts abbaa
  • ✓ rejects ε
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects ab
  • ✓ rejects aba
  • ✓ rejects baba
Test on 'aabab'
Answer:

(states and can also be merged into a single accepting trap state).

Example

Important Question 10 — Strings Not Containing 10110 as a Substring [2073 Chaitra]

Design a DFA that accepts the language

Verify your design with supporting examples.

Track the longest prefix of 10110 matched at the end of the string

Use 6 states with and :

  • : matched (no non-empty prefix of 10110).
  • : matched 1.
  • : matched 10.
  • : matched 101. (If 0 is read next, the last four bits are 1010, whose longest suffix that is a prefix of 10110 is 10, so .)
  • : matched 1011. (If 1 is read next, the last five bits are 10111, whose longest prefix match is 1, so ; if 0 is read next, 10110 is completed at .)
  • : dead state (10110 has occurred).
Transition table and state diagram
StateSymbol Symbol
Important Question 10 — Strings Not Containing 10110 as a Substring [2073 Chaitra]DFA
Important Question 10 — Strings Not Containing 10110 as a Substring [2073 Chaitra] 0, 1 1 0 1 0 1 0 1 0 1 0 q0 q1 q2 q3 q4 q5
State01
→*q0q0q1
*q1q2q1
*q2q0q3
*q3q2q4
*q4q5q1
q5q5q5
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts 1011
  • ✓ accepts 10101
  • ✓ accepts 00110
  • ✓ rejects 10110
  • ✓ rejects 1101101
  • ✓ rejects 1010110
Test on '1101101'
Answer:

where is the non-accepting trap state.

Example

Important Question 11 — Strings Having 01 and 10 as Substrings [2073 Shrawan]

Design a deterministic finite automaton (DFA) for the language

Verify your design by taking one accepted and one rejected string.

Analyze the condition for containing both 01 and 10

A binary string contains both 01 and 10 as substrings if and only if it undergoes at least two bit transitions:

  • Either it starts with 0 (state ), switches to 1 (01 seen, state ), and switches back to 0 (10 also seen, accepting state );
  • Or it starts with 1 (state ), switches to 0 (10 seen, state ), and switches back to 1 (01 also seen, accepting state ).
Construct the 6-state DFA for 01 AND 10 (and compare with 01 OR 10)
StateSymbol Symbol Meaning
Empty string
Only 's seen (00...)
01 seen, waiting for 0 (0...011...)
Only 's seen (11...)
10 seen, waiting for 1 (1...100...)
Both 01 and 10 seen (accepting)
Important Question 11 — Strings Having 01 and 10 as Substrings [2073 Shrawan]DFA
Important Question 11 — Strings Having 01 and 10 as Substrings [2073 Shrawan] 0, 1 0 1 1 0 0 1 1 0 0 1 q0 q1 q3 q2 q5 q4
State01
→q0q1q3
q1q1q2
q3q4q3
q2q5q2
*q5q5q5
q4q4q5
  • Machine-checked
  • ✓ accepts 010
  • ✓ accepts 101
  • ✓ accepts 0101011
  • ✓ accepts 00110
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 1
  • ✓ rejects 111
  • ✓ rejects 01
  • ✓ rejects 10
  • ✓ rejects 0011
  • ✓ rejects 1100

(Note: If the problem is interpreted as containing 01 or 10—i.e., any non-unary string containing at least one 0 and at least one 1—then and themselves become the accepting trap states, as drawn in the book on p. 104:)

Important Question 11 — Strings Having 01 and 10 as Substrings [2073 Shrawan]DFA
Important Question 11 — Strings Having 01 and 10 as Substrings [2073 Shrawan] 0, 1 1 0, 1 0 0 1 1 0 q0 q1 q3 q2 q4
State01
→q0q1q3
q1q1q2
q3q4q3
*q2q2q2
*q4q4q4
  • Machine-checked
  • ✓ accepts 01
  • ✓ accepts 10
  • ✓ accepts 0101011
  • ✓ accepts 100
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 1
  • ✓ rejects 000
  • ✓ rejects 111
Test on accepted string '0101011' and rejected string '111'
  • On the 6-state DFA (01 and 10):
  • On "111":
Answer:

The 6-state DFA accepts strings containing both 01 and 10.

Example

Important Question 12 — Strings Beginning with 0 and Ending with 10 [2071 Shrawan]

Design a DFA that accepts the language

Your design should accept 010, 011110, 000010, 01011010 and reject 1010, 0011, 01011.

Define the 5 states

Let , , , and :

  • : start state ().
  • : dead state (entered if the first symbol is 1).
  • : string started with 0 and currently ends in 0 (not 10).
  • : string started with 0 and currently ends in 1.
  • : string started with 0 and currently ends in 10 (accepting state).
Transition table and state diagram
StateSymbol Symbol
Important Question 12 — Strings Beginning with 0 and Ending with 10 [2071 Shrawan]DFA
Important Question 12 — Strings Beginning with 0 and Ending with 10 [2071 Shrawan] 0, 1 1 0 0 1 1 0 1 0 q0 q1 D q2 q3
State01
→q0q1D
q1q1q2
DDD
q2q3q2
*q3q1q2
  • Machine-checked
  • ✓ accepts 010
  • ✓ accepts 011110
  • ✓ accepts 000010
  • ✓ accepts 01011010
  • ✓ rejects ε
  • ✓ rejects 10
  • ✓ rejects 1010
  • ✓ rejects 0011
  • ✓ rejects 01011
Test on '011110'
Answer:

.


Exercises

Exercises

Question 1

Define finite state automata with its block diagram. [2080 Baishakh, 2079 Baishakh]

Definition of Finite State Automata (FA): A Finite State Automaton (or Finite Automaton) is an abstract mathematical model of computation consisting of a finite set of internal states and a finite control unit. It processes an input string of discrete symbols one symbol at a time from left to right, transitioning between internal states according to fixed rules, to decide whether the string belongs to a specified formal language.

Block diagram of a Finite State Automaton:

Input tape:   | a_1 | a_2 | ... | a_i | ... | a_n |
                              ^
                              |
                         Reading head (moves Left -> Right)
                        +------------+
                        |   States   |
                        |     q      |
                        +------------+
                        Finite control

Components of the automaton:

  1. Input Tape: Divided into a sequence of discrete cells, each holding exactly one symbol from the input alphabet . The tape contains the input string followed by blank space and is read-only.
  2. Reading Head: Points to the current symbol being scanned. It operates strictly unidirectionally, moving from left to right one cell per step without backtracking or writing.
  3. Finite Control: Maintains the current internal state . Upon reading each input symbol, it consults a transition function to change to a new state and directs the head to advance to the next cell.
Answer:

A finite state automaton is an abstract mathematical model of computation with a finite number of states, consisting of an input tape divided into cells, a read-only reading head that scans left-to-right, and a finite control unit that transitions between states according to a transition function.

Question 2

Explain the processing of a string by finite automata along with its block diagram. [2081 Chaitra]

Step-by-step processing of an input string:

  1. Initialization: The input string is placed on the input tape. The finite control starts in the designated initial state , and the reading head is positioned at the leftmost cell scanning symbol .
  2. Sequential Transition: For each symbol ():
    • The head reads .
    • The finite control computes the next state and changes state.
    • The head moves one cell to the right to scan .
  3. Halting & Decision: When all symbols have been read, the head reaches the end of the string.
    • If the final state (an accepting state), the string is accepted.
    • If , the string is rejected.

Block diagram during execution:

Tape:         | 0 | 1 | 0 | 1 | 1 |
                    ^
                    | Read symbol '1'
              +-----------+
              | State: q0 | ---> transitions to q1
              +-----------+
              Finite Control

Concrete illustrative DFA and trace: Consider a DFA that accepts all strings over ending in 01:

DFA for Strings Ending in 01DFA
DFA for Strings Ending in 01 0 1 0 1 0 1 q0 q1 q2
State01
→q0q1q0
q1q1q2
*q2q1q0
  • Machine-checked
  • ✓ accepts 01
  • ✓ accepts 101
  • ✓ accepts 001
  • ✓ accepts 1101
  • ✓ accepts 0101
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 1
  • ✓ rejects 10
  • ✓ rejects 00
  • ✓ rejects 010
  • Accepted string trace ():

Halts in ; thus is accepted.

  • Rejected string trace ():

Halts in ; thus is rejected.

Answer:

Processing begins with the finite control in the start state and the reading head at the leftmost symbol of the input string on the input tape. At each step, the reading head reads one symbol, the control transitions to the next state given by , and the head advances one cell right. When the end of the string is reached, is accepted if the current state is in and rejected otherwise.

Question 3

What is configuration of DFA? [2078 Kartik]

Formal definition of a configuration: A configuration (also known as an Instantaneous Description or ID) of a DFA is an ordered pair:

where:

  • denotes the current state of the finite control.
  • denotes the unconsumed suffix of the input string remaining on the tape to be read.

Step relation () between configurations: The single-step transition relation (or simply ) describes how the automaton progresses from one configuration to another:

for any state , symbol , and remaining string . The multi-step relation is the reflexive-transitive closure of :

  • in steps.
  • .

Acceptance in terms of configurations: A string is accepted by if and only if the initial configuration leads to a halting configuration whose state is accepting:

Concrete configuration trace example: Consider a DFA over that accepts strings containing 11 as a substring:

DFA for Substring 11DFA
DFA for Substring 11 0, 1 0 1 0 1 q0 q1 q2
State01
→q0q0q1
q1q0q2
*q2q2q2
  • Machine-checked
  • ✓ accepts 11
  • ✓ accepts 011
  • ✓ accepts 110
  • ✓ accepts 0110
  • ✓ accepts 1011
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 1
  • ✓ rejects 010
  • ✓ rejects 101
  • ✓ rejects 10

For input , the configuration trace is:

Since , the string is accepted.

Answer:

A configuration of a DFA is an ordered pair , where is the current state of the automaton and is the remaining unread suffix of the input string.

Question 4

Give the formal 5-tuple definition of a Deterministic Finite Automaton (DFA) and state the domain and codomain of its transition function.

Formal 5-tuple definition of a DFA: A Deterministic Finite Automaton (DFA) is formally defined as a 5-tuple:

where:

  1. (or ) is a non-empty, finite set of states.
  2. is a non-empty, finite set of symbols called the input alphabet.
  3. is the transition function.
  4. (or ) is the designated initial (start) state.
  5. is the set of final (accepting) states.

Domain and codomain of the transition function : The transition function is a total function specified as:

  • Domain: (the set of all pairs where and ).
  • Codomain: (the set of states).
  • Determinism: For every state and every symbol , produces exactly one unique destination state. No transition can produce multiple states or be undefined, and transitions on (empty string) are strictly disallowed.

Concrete illustrative 5-tuple example: Consider a DFA that accepts binary strings with an even number of 's:

DFA for Even Number of 0sDFA
DFA for Even Number of 0s 1 1 0 0 q0 q1
State01
→*q0q1q0
q1q0q1
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts 1
  • ✓ accepts 00
  • ✓ accepts 100
  • ✓ accepts 010
  • ✓ accepts 001
  • ✓ rejects 0
  • ✓ rejects 01
  • ✓ rejects 10
  • ✓ rejects 000
  • ✓ rejects 101

Its formal 5 tuples are:

  • , where , , , .
Answer:

A DFA is a 5-tuple where is a finite set of states, is a finite input alphabet, is the start state, is the set of final states, and is the transition function with domain and codomain .

Past exam questions for Theory of Computation

← Alphabets, Languages & Operations on LanguagesNFA, ε-NFA & Their Equivalence with DFA →