Finite State Machines & DFA Design
Open in the Padhaiko app2.1 Introduction to Finite Automata
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.
- The machine changes from one state to another in response to external inputs; each change of state is called a transition.
- An FSM is completely specified by its list of states, its initial (start) state, its accepting (final) states, and the input symbols that trigger each transition.
- Because the number of states is fixed, a finite automaton has a strictly fixed, finite memory capacity that cannot be expanded at runtime.
Applications of Finite Automata
Finite automata model hardware and software systems with a strictly bounded amount of memory:
- Embedded & Digital Controllers: Automatic door controllers, elevator controllers, household appliance controllers (dishwashers, electronic thermostats), and control units inside digital watches and calculators.
- Compiler Design (Lexical Analysis): The lexical analyzer (scanner) of a compiler simulates finite automata to tokenize identifiers, keywords, operators, and numeric literals.
- 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
- 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).
- Reading Head: Scans one tape cell at a time, moving strictly from left to right one cell per step.
- 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:
F(Front): A person is standing on the front pad in front of the doorway.R(Rear): A person is standing on the rear pad behind the doorway.B(Both): People are standing on both the front and rear pads (so opening a swinging door toward the rear would hit someone).N(Neither): No one is standing on either pad.
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 State | N (Neither) | F (Front) | R (Rear) | B (Both) |
|---|---|---|---|---|
| Closed | Closed | Open | Closed | Closed |
| Open | Closed | Open | Open | Open |
Modelling Closed as the start state and Open as the active/accepting state over gives the state diagram below:
| State | R | B | N | F |
|---|---|---|---|---|
| →Closed | Closed | Closed | Closed | Open |
| *Open | Open | Open | Closed | Open |
- Machine-checked
- ✓ accepts F
- ✓ accepts NF
- ✓ accepts FR
- ✓ accepts FB
- ✓ rejects ε
- ✓ rejects N
- ✓ rejects R
- ✓ rejects B
- ✓ rejects FN
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):
| State | 0 | 1 |
|---|---|---|
| →q1 | q1 | q2 |
| *q2 | q3 | q2 |
| q3 | q2 | q2 |
- Machine-checked
- ✓ accepts 1
- ✓ accepts 11
- ✓ accepts 1101
- ✓ accepts 0100
- ✓ rejects ε
- ✓ rejects 0
- ✓ rejects 10
- ✓ rejects 110
When is given the input string , computation proceeds left-to-right from the start state :
- Initial state: Start in state .
- First symbol (
1): Follow the transition labeled1from to . - Second symbol (
1): Follow the self-loop labeled1from to . - Third symbol (
0): Follow the transition labeled0from to . - Fourth symbol (
1): Follow the transition labeled1from to . - Decision: Since ends in the accepting state after the entire input is read, the string
1101is accepted. The set of all strings accepted by is called the language accepted by , denoted .
2.2 Deterministic Finite Automata (DFA) (Book 2.2.1)
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:
- is a finite, non-empty set of states,
- is a finite input alphabet,
- is the initial (start) state,
- is the set of final (accepting) states, and
- is the total transition function mapping each state-symbol pair to a unique next state.
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:
| State | a | b |
|---|---|---|
| →q0 | q0 | q1 |
| *q1 | q1 | q1 |
- Machine-checked
- ✓ accepts b
- ✓ accepts ab
- ✓ accepts ba
- ✓ accepts aba
- ✓ rejects ε
- ✓ rejects a
- ✓ rejects aa
- ✓ rejects aaa
Configuration and Yield Relation of a DFA
Let be a DFA.
- A configuration of is any ordered pair , where is the current state of and is the remaining unread portion of the input string. For example, means is in state with the reading head scanning the leftmost
aofababab. - The single-step yield relation (written ) relates two configurations when consumes one input symbol :
- The reflexive, transitive closure represents zero or more steps. A string is accepted by if and only if for some :
Worked Out Examples (Book Examples 2.1–2.6)
DFA for Strings with an Even Number of b's
Design a deterministic finite automaton that accepts the language
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 .
Reading a does not change the count of 's, whereas reading b toggles the parity between and :
| State | ||
|---|---|---|
| State | a | b |
|---|---|---|
| →*q0 | q0 | q1 |
| q1 | q1 | q0 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts a
- ✓ accepts bb
- ✓ accepts bab
- ✓ accepts ababa
- ✓ rejects b
- ✓ rejects ab
- ✓ rejects bbb
- ✓ rejects babb
babwith , , , and .
DFA for Strings Not Containing Three Consecutive b's
Design a DFA that accepts the language
Count how many consecutive 's occur at the end of the prefix read so far:
- : the prefix does not contain
bbband currently ends with consecutive 's (either empty or ending ina). - : the prefix does not contain
bbband ends with exactly oneb. - : the prefix does not contain
bbband ends withbb(two consecutive 's). - : trap (dead) state reached as soon as
bbbis encountered.
Whenever a is read in or , the run of consecutive 's resets to . Thus
| State | ||
|---|---|---|
| State | a | b |
|---|---|---|
| →*q0 | q0 | q1 |
| *q1 | q0 | q2 |
| *q2 | q0 | q3 |
| q3 | q3 | q3 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts b
- ✓ accepts bb
- ✓ accepts abbab
- ✓ accepts bbabb
- ✓ rejects bbb
- ✓ rejects abbb
- ✓ rejects bbba
- ✓ rejects abbba
abbab and note complementationSwapping accepting and non-accepting states () yields the complementary DFA accepting :
| State | a | b |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q0 | q2 |
| q2 | q0 | q3 |
| *q3 | q3 | q3 |
- Machine-checked
- ✓ accepts bbb
- ✓ accepts abbb
- ✓ accepts bbba
- ✓ accepts abbba
- ✓ rejects ε
- ✓ rejects b
- ✓ rejects bb
- ✓ rejects abbab
- ✓ rejects bbabb
, where reading a in resets to , reading b advances , and is a non-accepting trap state.
DFA for Strings Beginning with 01
Design a DFA that accepts the language
Let with , , , and :
- : initial state (no symbols read yet).
- : first symbol read was
0. - : prefix
01has been matched (accepting trap state). - : dead (rejecting trap) state for strings starting with
1or00.
| State | ||
|---|---|---|
| State | 0 | 1 |
|---|---|---|
| →q0 | q1 | q3 |
| q1 | q3 | q2 |
| q3 | q3 | q3 |
| *q2 | q2 | q2 |
- Machine-checked
- ✓ accepts 01
- ✓ accepts 010
- ✓ accepts 011
- ✓ accepts 01110
- ✓ rejects ε
- ✓ rejects 0
- ✓ rejects 1
- ✓ rejects 00
- ✓ rejects 10
- ✓ rejects 11
01110with , , for , and all other transitions entering dead state .
DFA for Strings Beginning with 01 of Even Length
Design a DFA that accepts the language
Let with , , , and :
- : start state (length , even).
- : read
0(length , odd). - : begins with
01and current length is even (accepting state, first reached at length ). - : begins with
01and current length is odd (non-accepting state). - : dead state (first two symbols were not
01).
Once 01 is matched at , every subsequent symbol (0 or 1) alternates between (even length) and (odd length):
| State | ||
|---|---|---|
| State | 0 | 1 |
|---|---|---|
| →q0 | q1 | q4 |
| q1 | q4 | q2 |
| q4 | q4 | q4 |
| *q2 | q3 | q3 |
| q3 | q2 | q2 |
- Machine-checked
- ✓ accepts 01
- ✓ accepts 0100
- ✓ accepts 0111
- ✓ accepts 011100
- ✓ rejects ε
- ✓ rejects 0
- ✓ rejects 010
- ✓ rejects 011
- ✓ rejects 0011
- ✓ rejects 1001
011100where , states and alternate on every symbol , and is the dead state.
DFA for Strings with Neither 00 Nor 11 as Substrings
Design a DFA that accepts the language
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
0from or a second consecutive1from ).
| State | ||
|---|---|---|
| State | 0 | 1 |
|---|---|---|
| →*q0 | q1 | q3 |
| *q1 | q2 | q3 |
| *q3 | q1 | q2 |
| q2 | q2 | q2 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts 0
- ✓ accepts 1
- ✓ accepts 01
- ✓ accepts 10
- ✓ accepts 01010
- ✓ rejects 00
- ✓ rejects 11
- ✓ rejects 0110
- ✓ rejects 010100
010100with as the non-accepting dead state.
DFA for Number of a's Multiple of 4
Design a DFA that accepts the language
Track the number of 's modulo using four states , where state () means . Since is a multiple of , and .
Reading b leaves the remainder unchanged (), whereas reading a increments the remainder modulo ():
| State | ||
|---|---|---|
| State | a | b |
|---|---|---|
| →*q0 | q1 | q0 |
| q1 | q2 | q1 |
| q2 | q3 | q2 |
| q3 | q0 | q3 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts b
- ✓ accepts aaaa
- ✓ accepts aaaba
- ✓ accepts baaaab
- ✓ rejects a
- ✓ rejects aa
- ✓ rejects aaa
- ✓ rejects aaaaa
aaabawith cycle and self-loops on .
Solutions to Important Questions (Questions 1–12, Book pp. 95–106)
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".
Let where , , , and :
- : (even , even ) — initial state.
- : (even , odd ) — accepting state.
- : (odd , even ).
- : (odd , odd ).
| State | ||
|---|---|---|
| State | b | a |
|---|---|---|
| →q0 | q1 | q2 |
| *q1 | q0 | q3 |
| q2 | q3 | q0 |
| q3 | q2 | q1 |
- Machine-checked
- ✓ accepts b
- ✓ accepts aab
- ✓ accepts aba
- ✓ accepts baa
- ✓ accepts aabbb
- ✓ rejects ε
- ✓ rejects a
- ✓ rejects ab
- ✓ rejects bb
- ✓ rejects aa
'aabbb', and "aabbb" ends in (accepted).
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 .
Track the last one or two identical symbols seen:
- : start state ().
- : ends in a single
0(not00). - : ends in
00(accepting). - : ends in a single
1(not11). - : ends in
11(accepting).
| State | ||
|---|---|---|
| State | 0 | 1 |
|---|---|---|
| →q0 | q1 | q3 |
| q1 | q2 | q3 |
| q3 | q1 | q4 |
| *q2 | q2 | q3 |
| *q4 | q1 | q4 |
- Machine-checked
- ✓ accepts 00
- ✓ accepts 11
- ✓ accepts 00110111
- ✓ accepts 01110100
- ✓ rejects ε
- ✓ rejects 0
- ✓ rejects 1
- ✓ rejects 01
- ✓ rejects 10
- ✓ rejects 0010
For :
For :
; both 00110111 (ending in ) and 01110100 (ending in ) are accepted.
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 .
- : valid string not ending in
b(accepting). - : valid string ending in a single
b(accepting). - : dead state reached once
bbappears (rejecting).
| State | a | b |
|---|---|---|
| →*q0 | q0 | q1 |
| *q1 | q0 | q2 |
| q2 | q2 | q2 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts a
- ✓ accepts b
- ✓ accepts ab
- ✓ accepts ba
- ✓ accepts baba
- ✓ rejects bb
- ✓ rejects abb
- ✓ rejects bba
- ✓ rejects baaababb
, and terminates in (rejected).
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.
If the binary prefix read so far has value , appending bit yields the new value :
- State (, accepting): , .
- State (): , .
- State (): , .
| State | 0 | 1 |
|---|---|---|
| →*q0 | q0 | q1 |
| q1 | q2 | q0 |
| q2 | q1 | q2 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts 0
- ✓ accepts 11
- ✓ accepts 110
- ✓ accepts 1001
- ✓ accepts 1100
- ✓ rejects 1
- ✓ rejects 10
- ✓ rejects 100
- ✓ rejects 101
- ✓ rejects 1010
- For (, divisible by ):
- For (, not divisible by ):
with .
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.
- : start state ().
- : last symbol was
a(waiting forbto completeab). - : accepting trap state (either
aborbbahas been seen). - : read a single
bwithout any priora(since anyafollowed bybwould already have triggeredab). - : read two or more 's (
bb...) without any priora(waiting forato completebba).
| State | ||
|---|---|---|
| State | a | b |
|---|---|---|
| →q0 | q1 | q3 |
| q1 | q1 | q2 |
| q3 | q1 | q4 |
| *q2 | q2 | q2 |
| q4 | q2 | q4 |
- Machine-checked
- ✓ accepts ab
- ✓ accepts bba
- ✓ accepts aab
- ✓ accepts bbba
- ✓ accepts bab
- ✓ rejects ε
- ✓ rejects a
- ✓ rejects b
- ✓ rejects ba
- ✓ rejects bb
- ✓ rejects baa
.
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.
Using the same 4-state construction as Worked Out Example 2.5 (, , , dead state ):
| State | Symbol | Symbol |
|---|---|---|
| State | 0 | 1 |
|---|---|---|
| →*q0 | q1 | q3 |
| *q1 | q2 | q3 |
| *q3 | q1 | q2 |
| q2 | q2 | q2 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts 0
- ✓ accepts 1
- ✓ accepts 0101
- ✓ accepts 1010
- ✓ rejects 00
- ✓ rejects 11
- ✓ rejects 01011010
01011010The string 01011010 enters the dead state upon reading the substring 11 and is rejected.
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
Track using states :
- (start and only accepting state), , (even number of 's).
- , , (odd number of 's).
Reading a cycles and ; reading b swaps , , and :
| State | Symbol | Symbol |
|---|---|---|
| State | a | b |
|---|---|---|
| →*q0 | q1 | q3 |
| q1 | q2 | q4 |
| q3 | q4 | q0 |
| q2 | q0 | q5 |
| q4 | q5 | q1 |
| q5 | q3 | q2 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts aaa
- ✓ accepts bb
- ✓ accepts aaabb
- ✓ rejects a
- ✓ rejects b
- ✓ rejects aa
- ✓ rejects ab
- ✓ rejects aaab
- ✓ rejects ababab
'aaabb'.
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.
Let , , , and :
- : start state ().
- : first symbol is
0. - : string started with
01(accepting trap state). - : string did not start with
01and currently ends in1. - : string did not start with
01and currently ends in0. - : string did not start with
01and currently ends in01(accepting state).
| State | Symbol | Symbol |
|---|---|---|
| State | 0 | 1 |
|---|---|---|
| →q0 | q1 | q3 |
| q1 | q4 | q2 |
| q3 | q4 | q3 |
| *q2 | q2 | q2 |
| q4 | q4 | q5 |
| *q5 | q4 | q3 |
- Machine-checked
- ✓ accepts 01
- ✓ accepts 01110
- ✓ accepts 1001
- ✓ accepts 0001
- ✓ rejects ε
- ✓ rejects 0
- ✓ rejects 1
- ✓ rejects 10
- ✓ rejects 0010
- ✓ rejects 1100
'01110' and '1001'- For
"01110"(starts with01):
- For
"1001"(ends with01):
.
Important Question 9 — Strings Having Either 'aa' or 'bb' as a Substring [2074 Chaitra]
Design a DFA that accepts the language
Let , , , and :
- : start state ().
- : no
aa/bbyet; last symbol wasa. - :
aahas been seen (accepting trap state). - : no
aa/bbyet; last symbol wasb. - :
bbhas been seen (accepting trap state).
| State () | Symbol | Symbol |
|---|---|---|
| State | a | b |
|---|---|---|
| →q0 | q1 | q3 |
| q1 | q2 | q3 |
| q3 | q1 | q4 |
| *q2 | q2 | q2 |
| *q4 | q4 | q4 |
- Machine-checked
- ✓ accepts aa
- ✓ accepts bb
- ✓ accepts aabab
- ✓ accepts abbaa
- ✓ rejects ε
- ✓ rejects a
- ✓ rejects b
- ✓ rejects ab
- ✓ rejects aba
- ✓ rejects baba
'aabab'(states and can also be merged into a single accepting trap state).
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.
10110 matched at the end of the stringUse 6 states with and :
- : matched (no non-empty prefix of
10110). - : matched
1. - : matched
10. - : matched
101. (If0is read next, the last four bits are1010, whose longest suffix that is a prefix of10110is10, so .) - : matched
1011. (If1is read next, the last five bits are10111, whose longest prefix match is1, so ; if0is read next,10110is completed at .) - : dead state (
10110has occurred).
| State | Symbol | Symbol |
|---|---|---|
| State | 0 | 1 |
|---|---|---|
| →*q0 | q0 | q1 |
| *q1 | q2 | q1 |
| *q2 | q0 | q3 |
| *q3 | q2 | q4 |
| *q4 | q5 | q1 |
| q5 | q5 | q5 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts 1011
- ✓ accepts 10101
- ✓ accepts 00110
- ✓ rejects 10110
- ✓ rejects 1101101
- ✓ rejects 1010110
'1101101'where is the non-accepting trap state.
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.
01 and 10A 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 to1(01seen, state ), and switches back to0(10also seen, accepting state ); - Or it starts with
1(state ), switches to0(10seen, state ), and switches back to1(01also seen, accepting state ).
01 AND 10 (and compare with 01 OR 10)| State | Symbol | 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) |
| State | 0 | 1 |
|---|---|---|
| →q0 | q1 | q3 |
| q1 | q1 | q2 |
| q3 | q4 | q3 |
| q2 | q5 | q2 |
| *q5 | q5 | q5 |
| q4 | q4 | q5 |
- 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:)
| State | 0 | 1 |
|---|---|---|
| →q0 | q1 | q3 |
| q1 | q1 | q2 |
| q3 | q4 | q3 |
| *q2 | q2 | q2 |
| *q4 | q4 | q4 |
- Machine-checked
- ✓ accepts 01
- ✓ accepts 10
- ✓ accepts 0101011
- ✓ accepts 100
- ✓ rejects ε
- ✓ rejects 0
- ✓ rejects 1
- ✓ rejects 000
- ✓ rejects 111
'0101011' and rejected string '111'- On the 6-state DFA (
01and10):
- On
"111":
The 6-state DFA accepts strings containing both 01 and 10.
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.
Let , , , and :
- : start state ().
- : dead state (entered if the first symbol is
1). - : string started with
0and currently ends in0(not10). - : string started with
0and currently ends in1. - : string started with
0and currently ends in10(accepting state).
| State | Symbol | Symbol |
|---|---|---|
| State | 0 | 1 |
|---|---|---|
| →q0 | q1 | D |
| q1 | q1 | q2 |
| D | D | D |
| q2 | q3 | q2 |
| *q3 | q1 | q2 |
- Machine-checked
- ✓ accepts 010
- ✓ accepts 011110
- ✓ accepts 000010
- ✓ accepts 01011010
- ✓ rejects ε
- ✓ rejects 10
- ✓ rejects 1010
- ✓ rejects 0011
- ✓ rejects 01011
'011110'.
Exercises
Exercises
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 controlComponents of the automaton:
- 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.
- 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.
- 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.
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.
Explain the processing of a string by finite automata along with its block diagram. [2081 Chaitra]
Step-by-step processing of an input string:
- 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 .
- 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 .
- 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 ControlConcrete illustrative DFA and trace: Consider a DFA that accepts all strings over ending in 01:
| State | 0 | 1 |
|---|---|---|
| →q0 | q1 | q0 |
| q1 | q1 | q2 |
| *q2 | q1 | q0 |
- 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.
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.
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:
| State | 0 | 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q0 | q2 |
| *q2 | q2 | q2 |
- 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.
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.
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:
- (or ) is a non-empty, finite set of states.
- is a non-empty, finite set of symbols called the input alphabet.
- is the transition function.
- (or ) is the designated initial (start) state.
- 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:
| State | 0 | 1 |
|---|---|---|
| →*q0 | q1 | q0 |
| q1 | q0 | q1 |
- 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 , , , .
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 .