Module
Nondeterministic Finite Automata, Equivalence, and Regular Expressions
Sign in to add this module to your path and practice.
About
NFAs (with and without ε-transitions), computation trees, subset (powerset) construction proving DFA≡NFA. Regular expressions and the equivalence of regexes, NFAs, and DFAs (Thompson / state-elimination style conversions). Closure properties via automata and regex.
Goal
Convert freely among DFA/NFA/ε-NFA/regex; prove equivalence of the models; use nondeterminism and regex to design recognizers more easily than pure DFAs; apply closure under union, concat, star, complement, intersection.
Prerequisites
Unlocks
Tutor
Ask questions about this module.
Hi — I'm your tutor for Nondeterministic Finite Automata, Equivalence, and Regular Expressions. Ask about the concepts, goal, or where you're stuck.