Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Regular expressions

Concise study notes on regular expressions: definitions, algebra, conversion to/from finite automata, key theorems (Kleene, Arden), common patterns and exam-style worked examples.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Regular expressions are a compact mathematical and practical way to describe regular languages (languages that can be recognised by finite automata). Engineers use them in compilers, lexical analysis, text processing, input validation, and when proving or designing finite automata and regular grammars for hardware and software systems.

Key ideas

  • Language: any set of strings over Σ.

  • Regular expression (RE): a formula built from symbols of Σ, the empty set symbol ∅, ε, and operators union, concatenation, and Kleene star; it denotes a language. Formally, the class of REs is defined inductively:

    1. ∅ is an RE and denotes the empty language ∅.
    2. ε is an RE and denotes {ε}.
    3. For each a ∈ Σ, a is an RE and denotes {a}.
    4. If r and s are REs denoting L(r) and L(s), then (r|s) (union), (r·s) (concatenation), and (r*) (Kleene star) are REs, denoting L(r) ∪ L(s), L(r)L(s), and (L(r))* respectively.
  • Regular language: a language describable by some RE, or equivalently accepted by some finite automaton (DFA/NFA). This equivalence is Kleene's theorem (stated below).

Precise statements universities expect:

  • Kleene's theorem (exact form): A language L over alphabet Σ is regular iff there exists a regular expression r over Σ such that L = L(r). Equivalently, the class of languages denoted by regular expressions equals the class of languages accepted by finite automata (DFA/NFA). Assumptions: standard RE syntax; automata are finite-state with no extra memory.

  • Thompson's construction (existence direction): For any RE r we can construct an NFA N(r) (with ε-transitions) such that L(N(r)) = L(r). Universities ask for the construction rules and a sketch of induction on the structure of r:

    • For base a: N(a) has two states, start → (a) → accept.
    • For ∅: N(∅) has a start and an accept state with no transition between them (the accept is unreachable).
    • For ε: N(ε) has a start state with an ε-transition to a distinct accept state.
    • For union r|s: build N(r) and N(s), add new start with ε to both starts, and new accept with ε from both accepts.
    • For concatenation rs: connect accept of N(r) with ε to start of N(s); start = start(N(r)), accept = accept(N(s)).
    • For star r*: add a new start and a new accept; add ε from the new start to start(N(r)) and to the new accept; add ε from accept(N(r)) to start(N(r)) and to the new accept. Describe exactly what to draw: for each operator, draw the small NFA fragment with labeled ε or symbol transitions; label the unique start and unique accept states.
  • From automaton to RE (state-elimination / algebraic method): Given a finite automaton, first convert it to a generalized NFA (GNFA) with a single start and single accept and all edges labeled by regular expressions (possibly ε or ∅); then eliminate states while replacing transitions by REs that summarise paths; the final result is a single RE. Universities often expect: create a single start and single accept (add new start connected by ε, and new accept with ε), then repeatedly remove intermediate states q and update each pair (i, j) by replacing existing edge R_ij with R_ij ∪ R_iq (R_qq)* R_qj. This is the core formula used during elimination.

  • Arden's lemma (used in algebraic method): If P and Q are languages over Σ and X is unknown, the equation X = P X ∪ Q has the unique solution X = P* Q provided ε ∉ P (or in algebraic form if P does not contain ε). This is often used to solve linear equations for unknown REs. State exact assumptions: P not containing ε ensures uniqueness.

  • Operators and algebraic laws often used in proofs/exams (you should be able to use and cite): associativity and precedence (star highest, then concatenation, then union), distributivity: r(s|t) = rs|rt etc., identities: ∅r = r∅ = ∅, εr = rε = r, r|∅ = r, r|r = r, (s|t)r = sr|tr, and star identities r* = ε | r r* = ε | r* r.

Formulas

List of syntax / symbols to remember (programming-style syntax first, then formal symbols). No SI units apply to these lines. | – union (or) in both formal RE and programming; example a|b means {"a","b"}. · or adjacency – concatenation; ab means string a followed by b, language {ab}. * – Kleene star; a* means zero or more repetitions of a (includes ε). + – one-or-more (positive closure); a+ means aa* (not part of the minimal formal definition but common in programs). ? – zero-or-one (optional) in programming REs; a? matches ε or a. . – in many programming REs, dot matches any single symbol (not used in pure formal REs unless alphabet defined). [] – character class in programming (e.g. [abc] matches a or b or c); not formal notation. () – grouping; (?: ) non-capturing group (programming detail). \ – escape character in programming REs to treat meta-characters literally. ^ and $ – anchors for start and end of string in programming REs. Formal symbols (mathematical): ∅ (empty language), ε (empty string), | (union), · or concatenation, * (Kleene star).

When to apply: use formal symbols in theory proofs and automata conversions; use programming syntax when implementing or writing patterns in tools like grep, Python, Java, JavaScript. Verify differences (e.g. +, ?, . are programming conveniences).

Worked examples

Example 1 — Build an RE and NFA (Thompson) for language: all strings over Σ = {a, b} that end with "ab". Answer (model exam text): The regular expression is (a|b)*ab. Reason: any prefix (including empty) then 'a' followed by 'b'. Thompson NFA construction (step-by-step):

  1. Build fragment for (a|b)* — first build for a|b: create new start s1 with ε-transitions to the starts of the a and b fragments, and add ε-transitions from their accepts to a new accept a1. For star, add new start S with ε to s1 and ε to new accept A; add ε from a1 back to s1 and to A.
  2. Concatenate with a then b: connect accept A of the star fragment by ε to the start of fragment for a, then connect accept of a fragment to start of b fragment; final accept is accept of b fragment.
  3. What to draw: draw the NFA fragments for a, b, union and star as above, clearly label start and final states and ε-transitions. The final NFA accepts L((a|b)*ab). Final answer: RE (a|b)*ab and the described NFA.

Example 2 — Convert a small DFA to a regular expression (state elimination). NFA: states {q0 (start), q1 (accept)}, alphabet {a}, transitions: q0 —a→ q0 and q0 —a→ q1. Model solution steps:

  1. Add new start s and new accept f with ε: s→ε→q0, q1→ε→f.
  2. Current labels: R_q0_q0 = a, R_q0_q1 = a, R_q1_q0 = ∅, R_q1_q1 = ∅.
  3. Eliminate q0: update R_s_q1 = R_s_q1 ∪ R_s_q0 (R_q0_q0)* R_q0_q1. Compute: R_s_q0 = ε, (R_q0_q0)* = a*, R_q0_q1 = a. So new R_s_q1 = ∅ ∪ ε · a* · a = a* a = a+. (Simplify: a+.)
  4. Then eliminate q1 and combine with f: final RE = a+ (because s→q1 then q1→f yields a+). Provide final simplified RE aa* (or a+ in programming syntax), meaning one or more a's. Give final boxed expression: a+.

Example 3 — Use Arden's lemma to solve linear equations for REs. Problem: For DFA with states p (start) and q (final), transitions p —a→ p, p —b→ q, q —a→ q, q —b→ q. Write equations and solve.

  1. Let X_p be set of strings from p to final, X_q from q to final. Equations: X_p = a X_p ∪ b X_q ∪ (ε if p is also final; here not) X_q = (a|b) X_q ∪ ε (since q is final)
  2. Solve X_q first: by Arden, X_q = (a|b)* ε = (a|b)*.
  3. Substitute into X_p: X_p = a X_p ∪ b (a|b). Applying Arden again: X_p = a b (a|b)*. Final RE for strings from start to final: a* b (a|b)*. Show each substitution step clearly; mention assumption ε ∉ a (or a does not include ε) when applying Arden.

Common mistakes

  • Forgetting to add a new unique start and accept state before doing state elimination (makes elimination messy).
  • Applying Arden's lemma when the coefficient language may contain ε; always check the condition for uniqueness.
  • Incorrect precedence: union has lower precedence than concatenation and star—write parentheses to avoid ambiguity.
  • Thinking every context-free language is regular; regular languages are strictly less powerful than CFLs.

For your exam

Question types usually seen:

  • Definitions and short notes: define regular expression, Kleene's theorem, Arden's lemma — give short proof sketches.
  • Constructions/derivations: show Thompson's construction for a given RE or convert a RE to an NFA diagram (draw fragments and label ε transitions).
  • Conversions: convert small DFA/NFA to a regular expression using state-elimination or algebraic equations (show each elimination/update formula).
  • Short proofs: prove an equivalence using induction on RE structure or show closure properties (union, concatenation, star) with automata constructions.
  • Practical/implementation: explain differences between formal RE and a programming RE flavor. A full-marks answer includes: formal definitions in first lines, clear diagrams with labeled states and transitions when required, step-by-step application of algorithm (Thompson or elimination), and final simplified RE. Mention assumptions (alphabet, presence/absence of ε in intermediate languages) and justify use of Arden's lemma when applied.

Quick check

  1. Give a regular expression for all binary strings that contain at least one 1.
  2. State Arden's lemma precisely and when it can be applied.
  3. What is the Kleene star of the empty set ∅* ? Answers: 1. (0|1)*1(0|1)* 2. If X = P X ∪ Q and ε ∉ P then the unique solution is X = P* Q (apply when P does not contain ε) 3. ∅* = {ε} (only the empty string).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?