Alphabets, Strings and Languages
Every model in the theory of computation (finite automata, pushdown automata, Turing machines) processes strings built from a fixed finite alphabet. A language is simply a set of strings.
Theory of Computation · topic
Regular expressions
Operators and precedence, the identities that hold and the look-alikes that do not, writing an expression for a described language, equivalence checks with short counterexamples, counting strings of a given length, Thompson's regex to epsilon-NFA construction, epsilon-closure, state elimination and Arden's rule.
Study this topic
Regular Expressions
A regular expression (RE) is a concise notation for a language built from single symbols by union, concatenation and Kleene star.
Equivalence of Regular Expressions and Finite Automata
Regular expressions and finite automata define the same class of languages. One direction builds an ε-NFA from an expression (Thompson's construction). The other eliminates states from a DFA (or NFA) until a single regular expression remains.
Regular expressions cheat sheets
One-page visual sheets for this topic, in the sheet library on the store. Previews are free; the full sheets come with the subject pack.