Writing regexes, identities and equivalence

1. How is ab* parsed?
   Stuck? Peek at 2.1.1 Regular expressions: syntax and meaning

   • Atoms ∅, ε, a; operators r + s (∪), rs (concat), r* (star); r⁺ = rr*.
   • Precedence: * > concatenation > +.
   • Kleene: regular ⇔ described by a regex.
   • Patterns: Σ* = (a+b)*; ends w = (a+b)*w; starts w = w(a+b)*; contains w = (a+b)*w(a+b)*; even length = ((a+b)(a+b))*; exactly two a’s = b*ab*ab*.

   Read lesson 2.1.1

2. Minimal DFA for “no two consecutive a’s” has how many states?
   Stuck? Peek at 1.3.2 Partition and table-filling methods

   • Partition: remove unreachable; P₀ = {F, Q−F}; split by signatures w.r.t. previous partition; stop when stable.
   • Table filling: n(n−1)/2 cells; mark (F, non-F); propagate “successor pair marked ⇒ mark”; unmarked = equivalent.
   • Count by distinct futures: list situations with different accepted continuations, include dead / satisfied states.
   • Exactly k of a symbol: k + 2 states; at least k: k + 1; at most k: k + 2.

   Read lesson 1.3.2

3. Is the minimal DFA unique?
   Stuck? Peek at 1.3.1 Unreachable, equivalent and distinguishable states

   • Step 0: delete unreachable states (BFS from q₀).
   • p ≡ q ⇔ ∀w: δ̂(p,w) ∈ F ⇔ δ̂(q,w) ∈ F. Distinguishable ⇔ some w separates.
   • ≡₀ = {F, Q−F}; ≡ₖ₊₁ splits by where symbols lead w.r.t. ≡ₖ; stop when stable.
   • Merge classes → minimal DFA, unique up to renaming.

   Read lesson 1.3.1

Two programmers write different search patterns for “binary strings without two consecutive 1s”. Are their patterns the same? Testing a few strings proves nothing if they agree; a single disagreement proves they differ. GATE loves this: four regexes, “which ones are equivalent to (a + b)*?”. You need identities for simplification and a fast hunt for counterexamples.

Are a*b* and (ab)* the same language? Are (a + b)* and (a*b*)* the same?

Prediction check

a*b* vs (ab)*: different — “aab” ∈ a*b* but ∉ (ab)*. (a+b)* vs (a*b*)*: same — every symbol is itself an a*b* block, and nothing outside Σ* can appear.

Identities to know cold

Famous non-identities

• (r + s)* ≠ r* + s* (ab is in the left only).
• (rs)* ≠ r*s* (aab separates (ab)* from a*b*).
• (r + s)* ≠ r*s* (ba separates).
• r*s* ≠ (rs)*; (r*s*)* ≠ r*s*.
• rs ≠ sr in general.

Writing regexes from descriptions

1. Find the skeleton: what must appear, in what order.
2. Fill the gaps with what is allowed between them.
3. Test on the shortest strings and on edge cases (ε, single symbols).

• At least one a: (a+b)*a(a+b)* or b*a(a+b)*.
• At most one a: b*(ε + a)b*.
• No two consecutive a’s: (b + ab)*(ε + a) — every a is followed by b except possibly the last.
• Number of a’s divisible by 3: (b*ab*ab*ab*)* + b* → simplifies to b*(ab*ab*ab*)*.
• Starts and ends with different symbols: a(a+b)*b + b(a+b)*a.

Checking equality of two regexes

1. Compare the shortest strings of each (ε? length 1? length 2?) — most GATE distractors die here.
2. Look for a structural difference: a string one forces (like ab adjacency) the other forbids.
3. If you suspect equality, transform one into the other with identities.
4. The guaranteed method: build both minimal DFAs and compare (the minimal DFA is unique).

Putting it together

• Learn the identities: ∅* = ε, (r*)* = r*, (r+s)* has many equal forms, (rs)*r = r(sr)*.
• (r+s)* ≠ r* + s* ≠ r*s*; (rs)* ≠ r*s*.
• Compare shortest strings first; one counterexample settles inequality.

no two consecutive a's:   (b + ab)*(ε + a)
 strings ≤ 3:  ε  a  b  ab  ba  bb  aba  abb  bab  bba  bbb      (11 = 1+2+3+5 Fibonacci-like)
 check "aab": (b+ab)* can't make "aa"  → not in L ✓

equivalence hunt:  r1 = (a+b)*      r2 = a* + b*
 length 2:  r1 gives aa ab ba bb       r2 gives aa bb
 counterexample "ab" → r1 ≠ r2

Regexes and DFAs describe the same languages — but so far that is a claim. Next chapter proves it: converting a regex into an ε-NFA (Thompson), and an automaton back into a regex (state elimination, Arden).

1. MSQ

   Which are equivalent to a*?

   1. (a*)*
   2. ε + aa*
   3. a*a*
   4. a⁺
2. MSQ

   Which strings distinguish (ab)* from a*b* (belong to exactly one of them)?

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

   Regex for binary strings with at most one 0:

   1. 1*01*
   2. 1*(0 + ε)1*
   3. (1 + 0)*
   4. 1*0*1*
4. NAT

   How many strings of length 4 are in L((b + ab)*(ε + a))?

   Write your answer before opening the key.

5. MCQ

   (rs)*r equals:

   1. r(sr)*
   2. r*s*r
   3. (sr)*r
   4. rs*r

• regex identities
• shifting identity (rs)*r = r(sr)*
• equivalent regexes
• counterexample string

1. Is (a+b)* = a* + b*?
   Reveal answer

   No — ab is only in the left side.
2. (a+b)* equals which other forms?
   Reveal answer

   (a*b*)*, (a*+b*)*, a*(ba*)*, (a*b)*a*
3. Regex: no two consecutive a’s over {a,b}?
   Reveal answer

   (b + ab)*(ε + a)
4. ε + rr* = ?
   Reveal answer

   r*
5. (rs)*r = ?
   Reveal answer

   r(sr)*

• Count strings of length n with no two consecutive a’s: Fibonacci — 1, 2, 3, 5, 8, 13 for n = 0..5.
• Fast regex-equality check: write the strings of length 0, 1, 2 for each option. The odd one out shows itself.