Chapter 2 · Watch, then practise
Finite Automata
Construct finite-state recognizers and explain where their memory limits matter.
3 questions · 3 with related videos. Matches are based on playlist titles; broader background matches are labeled.
What to study
- DFA transitions
- NFA acceptance
- Subset construction
- Regular languages
- Pumping lemma
Chapter playlists
Choose a playlist
Notes
Lec-13: DFA for Even a and Even b | Even a Odd b | Odd a and Even b | Odd a Odd b | TOC
Gate Smashers · 9:35
Shows parity-based DFA design with a related alphabet; the binary odd-ones machine is specified below.
1. A two-state DFA
Construct a DFA over {0, 1} accepting strings with an odd number of 1s.
Use states E and O for even and odd counts. Start in E and accept only O. On 0, remain in the current state; on 1, switch states. For 1011 the trace is E → O → O → E → O, so it is accepted. ε is rejected.
Lec-20: Convert NFA to DFA with example in Hindi | How to Convert NFA to DFA
Gate Smashers · 9:37
Related NFA-to-DFA conversion lesson for understanding states that represent sets of possibilities.
2. Nondeterminism and conversion
What does one DFA state represent when converting an NFA to a DFA?
It represents a set of possible NFA states after the input prefix. On a symbol, collect all reachable states and include any ε-moves. A set is accepting when it contains at least one accepting NFA state. With n NFA states there are at most 2ⁿ subsets, although many may be unreachable.
Lec-33: Pumping lemma for regular languages in TOC with examples
Gate Smashers · 12:00
Supplementary pumping-lemma lesson; the proof for this language is given in the answer.
3. Proving non-regularity
Use the pumping lemma to show that L = {0ⁿ1ⁿ | n ≥ 0} is not regular.
Assume a pumping length p and choose 0ᵖ1ᵖ. Every allowed split xyz with |xy| ≤ p and |y| > 0 puts y entirely among the zeros. Pumping y zero times leaves fewer zeros than ones, outside L. Since every allowed split fails, the assumption of regularity is contradicted.