โ† Theory of Computation learning path
Theory of Computation ยท Module 4 of 10

Regular expressions

Describing regular languages with patterns.

๐Ÿ“– Key ideas

  1. Regular expressions use union (+ or |), concatenation and star (*).
  2. Every regular expression has an equivalent finite automaton and vice versa (Kleene's theorem).
  3. (0 + 1)* means all binary strings; (0 + 1)*1 means strings ending in 1.
  4. Arden's theorem helps convert automata to regular expressions.
  5. 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*