ConceptSystems & CS
Regular expressions
A way of using patterns to validate inputs or to extract information from strings.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
String2Alphabet1Conditional statement1HTML form validation1Language1Programming basics1Python strings1Regular operations1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
2Each in their own terms, from the easiest level.
David J. Malan
Michael Sipser
Expressions built from atomic elements like symbols and empty strings using regular operations of union, concatenation, and star.
Lectures that assume it
6- Speculations on Test-Time Scaling for Large Language Models (o1)
- Let's Build the GPT Tokenizer: Byte Pair Encoding & Unicode Internals
- Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA
- Regular Pumping Lemma, Conversion of FA to Regular Expressions
- What Compilers Can and Cannot Do
- Provably Intractable Problems, Oracles
Connections
18The lectures that define it or assume it, and the concepts next to it.
Concepts9
- String
- Alphabet
- Conditional statement
- Language
- Generalized nondeterministic finite automaton
- Automatic verifier