Grokking Modern System Design Interview for Engineers & Managers
Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.
A deterministic finite automaton has one transition from one state to another. On the other hand, a nondeterministic finite automaton has one or more than one transition from one state to another or itself.
Every deterministic finite automaton is a nondeterministic finite automaton but the reverse is not true.
Assume an NFA for a language L with
It is converted to a DFA
Note: While converting an NFA with n states to a DFA, 2^{n}^{ }possible set of states can be reachable but not necessarily reached in the DFA.
The following general set of rules are followed to convert a nondeterministic finite automaton to a deterministic finite automaton:
Let's consider the following nondeterministic finite automaton that accepts the language
For this NFA,
state | a | b |
q_{0} | q_{1}, q_{2} | q_{4} |
q_{1} | q_{0} | - |
q_{2} | q_{3} | - |
q_{3} | - | q_{0} |
q_{4} | - | - |
Checks if
Add the first state to
For each state in
state | a | b |
q_{0} | q_{1}, q_{2} | q_{4} |
state | a | b |
q_{0} | q_{1}, q_{2} | q_{4} |
q_{1}, q_{2} | q_{0}, q_{3} | - |
q_{4} | - | - |
state | a | b |
q_{0} | q_{1}, q_{2} | q_{4} |
q_{1}, q_{2} | q_{0}, q_{3} | - |
q_{4} | - | - |
q_{0}, q_{3} | q_{1} | q_{0}, q_{4} |
state | a | b |
q_{0} | q_{1}, q_{2} | q_{4} |
q_{1}, q_{2} | q_{0}, q_{3} | - |
q_{4} | - | - |
q_{0}, q_{3} | q_{1}, q_{2} | q_{4} |
q_{1} | q_{0} | - |
q_{0}, q_{4} | q_{1}, q_{2} | q_{4} |
Combine all the states in the last obtained transition table and show appropriate transitions. In case a transition is not defined for input, make a transition to the trap state.
For this DFA,
RELATED TAGS
CONTRIBUTOR
Grokking Modern System Design Interview for Engineers & Managers
Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.