FSAs and Regular Expressions
FSAs and Regular Expressions is a core topic in the ACSL Senior division (Contest 3). The following subtopics reflect the concepts students are expected to master.
Subtopics
- Basics
- Regular Expression Identities
- Idempotence of Kleene Star ((a*)* = a*)
- Commutativity Claim
- Kleene Star Identity Law (aa* ∪ λ = a*)
- Distributive Law (a(b ∪ c) = ab ∪ ac)
- Star Rotation (a(ba)* = (ab)*a)
- Star–Union Expansion ((a ∪ b)* = (a* ∪ b*)*)
- Kleene Star Factorization ((a ∪ b)* = (a*b*)*)
- Arden’s Theorem (Right-Linear Form)
- RegEx in Practice
Want to practice FSAs and Regular Expressions questions?
Sign in to access full ACSL-style problems with instant AI-powered grading and feedback.