Regular expressions: syntax and meaning

1. What is L* for L = ∅?
   Stuck? Peek at 0.3.3 Operations on languages

   • L₁L₂ = {xy}; L{ε} = L; L∅ = ∅; not commutative.
   • L⁰ = {ε}; L* = ⋃Lⁿ (n≥0); L⁺ = LL*; L* = L⁺ ∪ {ε}; (L*)* = L*.
   • ∅* = {ε} = {ε}*; ∅⁺ = ∅.
   • L̅ = Σ* − L (include ε!). (L₁L₂)ᴿ = L₂ᴿL₁ᴿ.
   • Counting: C(n,r); fixed positions 2^(free); inclusion–exclusion; complement counting.

   Read lesson 0.3.3

2. Moore machine output length for input length n?
   Stuck? Peek at 1.4 Mealy and Moore machines

   • Moore: λ : Q → Δ; output length n+1. Mealy: λ : Q × Σ → Δ; output length n.
   • Moore → Mealy: same states, λ'(q,a) = λ(δ(q,a)). Mealy → Moore: ≤ |Q|·|Δ| states.
   • No accepting states; equivalence ignores Moore’s first output.

   Read lesson 1.4

3. What does Myhill–Nerode say about aⁿbⁿ?
   Stuck? Peek at 1.3.3 Myhill–Nerode theorem

   • x ≡_L y ⇔ ∀z: xz ∈ L ⇔ yz ∈ L. Right-invariant equivalence.
   • L regular ⇔ finite index; index = #states of minimal DFA (incl. dead class).
   • Infinitely many pairwise distinguishable strings ⇒ not regular. aⁿbⁿ: strings aⁱ separated by bⁱ.

   Read lesson 1.3.3

You type *.pdf to find files, or a pattern like [0-9]+ in a search box. You are describing a whole language with a tiny formula. In TOC that formula is a regular expression (regex). It describes the same languages DFAs accept — but instead of a machine that checks strings, it is a recipe that builds them. GATE asks you to read, write and compare regexes in nearly every paper.

Using only “or”, “followed by” and “repeat any number of times”, can you describe the language “all strings over {a, b} that end with b”?

Prediction check

Yes: “(a or b), repeated any number of times, followed by b” — written (a + b)*b. Anything, then a final b.

Building blocks

GATE writes union as +; many books and tools write | or ∪. Same meaning. r⁺ is shorthand for rr* (one or more).

Precedence

Like × before + in arithmetic: star binds tightest, then concatenation, then union.

• ab* means a(b*) — not (ab)*.
• a + bc means a + (bc) — not (a+b)c.
• a + b* means a + (b*).

Reading a regex in plain English

Translate piece by piece:

• (a + b)* — “any string over {a,b}”, i.e. Σ*.
• (a + b)*abb — “ends with abb”.
• a(a + b)* — “starts with a”.
• (a + b)*aa(a + b)* — “contains aa”.
• ((a + b)(a + b))* — “even length”.
• b*ab*ab* — “exactly two a’s”.
• (a + ε)(b + ab)* — no two a’s in a row (see 2.1.2).

Regex = regular language

Kleene’s theorem: a language is regular (accepted by some DFA) if and only if some regular expression describes it. Chapter 2.2 proves both directions by conversions. So regexes, DFAs, NFAs and ε-NFAs are four faces of one family.

Putting it together

• A regex is built from ∅, ε, symbols with +, concatenation and *.
• Precedence: star, then concatenation, then union.
• Regexes describe exactly the regular languages (Kleene).

parse tree of  a + b c*      (star, then concat, then union)

        +
       / \
      a   ·            L = {a} ∪ {b, bc, bcc, bccc, ...}
         / \
        b   *
            |
            c

  regex              plain English                          shortest strings
  (a+b)*b            ends with b                            b, ab, bb
  a(a+b)*b           starts with a and ends with b          ab, aab, abb
  (ab)*              ab repeated                            ε, ab, abab
  a*b*               some a's then some b's                 ε, a, b, aa, ab
  (a*b*)*            anything                               = (a+b)*

We can read regexes. Next: writing them from descriptions, the identities that simplify them, and the classic GATE task — deciding whether two different-looking regexes describe the same language.

1. MCQ

   Which string is NOT in L(a(a + b)*b)?

   1. ab
   2. aab
   3. abab
   4. aba
2. MCQ

   How is a + bc* parsed?

   1. ((a + b)c)*
   2. a + (b(c*))
   3. (a + b)(c*)
   4. (a + bc)*
3. NAT

   How many strings of length 3 are in L((a + b)*a(a + b)(a + b))?

   Write your answer before opening the key.

4. MSQ

   Which regexes describe exactly the strings over {a,b} of even length?

   1. ((a + b)(a + b))*
   2. (aa + ab + ba + bb)*
   3. (a + b)*(a + b)*
   4. (a + b)(a + b)*
5. MCQ

   L(∅*) is:

   1. ∅
   2. {ε}
   3. Σ*
   4. undefined

• regular expression (regex)
• L(r)
• union r + s
• concatenation rs
• Kleene star r*, r⁺
• precedence (* > concat > +)
• Kleene’s theorem (regex ⇔ regular)

1. Regex precedence order?
   Reveal answer

   Star, then concatenation, then union.
2. Regex for “ends with abb” over {a,b}?
   Reveal answer

   (a+b)*abb
3. Regex for “exactly two a’s” over {a,b}?
   Reveal answer

   b*ab*ab*
4. Kleene’s theorem?
   Reveal answer

   A language is regular iff some regular expression describes it.