Theory Of Computation 2024-25
Question:
Design DFA to accept strings of a's and b's which ends with string ab
1.
States:
There are three states visible: q0, q1, and q2.
Each state is represented by a yellow circle and is uniquely labeled:
o q0: Likely the start state.
o q1: A state representing partial progress towards "ab".
o q2: Could be the accepting state, representing the completion of "ab".
Layout:
The states are placed without any transitions or connections between them yet. The
connections (arrows) are what define the movement between states based on
inputs.
2.
Dept Of ISE, JIT Page 1
Theory Of Computation 2024-25
States:
Represented by the circles labeled "q0" and "q1". These states represent different conditions or
modes that the system can be in.
Transitions:
Represented by the arrows between the states. Each arrow is labeled with the input or event that
triggers the transition.
3.
Dept Of ISE, JIT Page 2
Theory Of Computation 2024-25
Initial State: The initial state is "q0", indicated by the arrow pointing into it.
Transitions:
From "q0" on input "a": Transition to
"q1" From "q1" on input "b": Transition
to "q0" 4.
Initial State: The initial state is "q0", indicated by the arrow pointing into it.
Transitions:
From "q0" on input "a": Transition to "q1"
From "q1" on input "b": Transition to "q0"
From "q1" on input "c": Transition to "q2"
From "q2" on input "a": Transition to "q0"
5.
Dept Of ISE, JIT Page 3
Theory Of Computation 2024-25
Initial State: The initial state is "q0", indicated by the arrow pointing into it.
Transitions:
From "q0" on input "a": Transition to "q1"
From "q1" on input "b": Transition to "q0"
From "q1" on input "c": Transition to "q2"
From "q2" on input "a": Transition to "q0"
6.
Dept Of ISE, JIT Page 4
Theory Of Computation 2024-25
Initial State: The initial state is "q0", indicated by the arrow pointing into it.
Transitions:
From "q0" on input "a": Transition to "q1"
From "q1" on input "b": Transition to "q0"
From "q1" on input "c": Transition to "q2"
From "q2" on input "a": Transition to "q0"
Dept Of ISE, JIT Page 5
Theory Of Computation 2024-25
7.
Initial State: The initial state is "q0", indicated by the arrow pointing into it.
Transitions:
From "q0" on input "a": Transition to "q1"
From "q1" on input "b": Transition to "q0"
From "q1" on input "c": Transition to "q2"
From "q2" on input "a": Transition to "q0"
Language Accepted:
This FSM accepts a broader range of strings. It's more challenging to precisely define
the language without further analysis. However, it's clear that it accepts strings that
involve transitions between all three states.
Key Points:
Dept Of ISE, JIT Page 6
Theory Of Computation 2024-25
The FSM has three states, making its behavior more complex.
The transitions are still deterministic, ensuring a clear path for each state-
input combination.
Dept Of ISE, JIT Page 7
