โ Theory of Computation learning pathTheory of Computation ยท Module 4 of 10
Regular expressions
Describing regular languages with patterns.
๐ Key ideas
- Regular expressions use union (+ or |), concatenation and star (*).
- Every regular expression has an equivalent finite automaton and vice versa (Kleene's theorem).
- (0 + 1)* means all binary strings; (0 + 1)*1 means strings ending in 1.
- Arden's theorem helps convert automata to regular expressions.
- Practical regex (grep, Python re) adds features such as character classes and backreferences.
๐ก Real-life example: A regular expression is a search pattern, like telling a librarian "any book whose title starts with The and ends with a number".
Regular expressionPattern describing a regular language
Kleene's theoremRegular expressions and finite automata are equivalent
UnionEither of two patterns
Arden's theoremMethod to solve R = Q + R P as R = Q P*