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 nondeterministic finite automaton has zero, one, or more than one transition from one state to another or itself. In epsilon nondeterministic finite automaton, null or epsilon transitions take place from one state to another state.
An epsilon NFA is formed by a regular expression for a language. This epsilon NFA is then converted to a simple NFA. The obtained NFA is then used for making a deterministic finite automaton.
Note: To learn how to convert an NFA to a DFA, click here.
Suppose an NFA
The null closure of
To convert an epsilon NFA to NFA, the null closure method makes use of the following general set of rules.
Consider the following epsilon NFA,
Find the null closure of all the states by the property defined before.
state | set |
q0 | {q0, q1, q3} |
q1 | {q1, q3} |
q2 | {q2} |
q3 | {q3} |
Implement the process for all states for the given inputs in order.
state | 0 | 1 |
q0 | {q0, q1, q2, q3} | - |
q1 | {q2, q3} | - |
q2 | - | {q1, q3} |
q3 | {q3} | - |
Make the NFA through the transitions obtained in the previous step.
All states that have
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.