Unit 1: Finite Automata
DFA and NFA
15 min read · 20% complete
Explanation
A finite automaton is a simple machine with states. It reads input one symbol at a time and moves between states.
If it ends in an accepting state, the input is accepted.
Key exam points
- DFA and NFA have equal expressive power
- Subset construction may cause exponential blow-up
- Myhill-Nerode gives the minimal DFA
Previous year questions
Convert the given NFA into an equivalent DFA using subset construction.
2024 · 10 marks
State and prove the pumping lemma for regular languages.
2023 · 8 marks
Practice quiz
An NFA with n states converts to a DFA with at most: