Conversion of Regular Expressions to Finite Automata
Snap together tiny machines like Lego bricks, one per symbol and one per operator, and the whole pattern becomes an automaton.
What this unit covers
Unit 3: Regular Expressions and Regular Languages
- 1 Regular Expressions and Regular SetsA one-line pattern that names a whole infinite language, and the algebra that lets you simplify it. · 12 min
- 2 Conversion of Regular Expressions to Finite AutomataSnap together tiny machines like Lego bricks, one per symbol and one per operator, and the whole pattern becomes an automaton. · 12 min
- 3 Conversion of Finite Automata to Regular ExpressionsRemove the states one by one, writing what each one did onto the arrows, until only the pattern is left. · 13 min
- 4 The Pumping Lemma for Regular LanguagesA machine with p rooms that walks p steps must enter some room twice, and that one fact proves which languages no automaton can recognise. · 14 min
- 5 Closure and Decision Properties of Regular LanguagesCombine two regular languages almost any way you like and the result is still regular, and that fact is a tool for proofs. · 13 min