L2.1 · Regular expressions

Chapter recap

Regexes use ∅, ε, symbols, +, concatenation and *, with precedence * > concat > +. Kleene’s theorem: regexes describe exactly the regular languages. Identities: ∅* = ε* = ε, r∅ = ∅, (r*)* = r*, ε + rr* = r*, (rs)*r = r(sr)*, (r+s)* = (r*s*)* = r*(sr*)*. Non-identities: (r+s)* ≠ r* + s*, (rs)* ≠ r*s*. To compare regexes, list the shortest strings or find a counterexample.

Merged rule card

From 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*.

From 2.1.2 Writing regexes, identities and equivalence

∅ + r = r; ∅r = ∅; εr = r; ∅* = ε* = ε; (r*)* = r*; r*r* = r*; ε + rr* = r*; (rs)*r = r(sr)*.
(r+s)* = (r*s*)* = (r*+s*)* = r*(sr*)* = (r*s)*r*.
≠: (r+s)* vs r*+s* vs r*s*; (rs)* vs r*s*.
No “aa”: (b+ab)*(ε+a). At most one a: b*(ε+a)b*. Even #0: 1*(01*01*)*.
Equality: compare shortest strings; counterexample kills; identities or minimal DFAs prove.

Practice questions

MCQ
Which regex describes strings over {0,1} containing 00 or 11?
1. (0+1)*(00+11)(0+1)*
2. (00+11)*
3. (0+1)*00(0+1)*11
4. 0*1*
MSQ
Which equal (0 + 1)*?
1. (0*1*)*
2. (0* + 1*)*
3. 0*(10*)*
4. (01 + 1)*0*
NAT
Number of strings of length 3 in L(a*b*)?
Write your answer before opening the key.
MCQ
L((a + ε)(b + ε)) has how many strings?
1. 2
2. 3
3. 4
4. infinite
MCQ
Which is the empty language?
1. ε*
2. ∅*
3. a∅
4. ε + ∅
NAT
Strings of length 5 over {a,b} with no two consecutive a’s?
Write your answer before opening the key.
MSQ
Which describe “second symbol is b” over {a,b}?
1. (a+b)b(a+b)*
2. ab(a+b)* + bb(a+b)*
3. (a+b)*b(a+b)
4. b(a+b)*
MCQ
(a + b)*a(a + b)*a(a + b)* describes:
1. exactly two a’s
2. at least two a’s
3. aa as a substring
4. even number of a’s

Answer key

Reveal answers when you’re ready

A — Anything, a doubled symbol, anything.
- B: Only strings made of doubled blocks.
- C: Requires both, in order.
- D: Unrelated.
ABC — Identities; D cannot produce 00 before a 1.
- D: “001” is not generated.
4 — aaa, aab, abb, bbb.
C — ε, a, b, ab.
- A: Forgot ε and ab.
- B: Forgot one.
- D: No star.
C — Concatenation with ∅ is ∅.
- A: {ε}.
- B: {ε}.
- D: {ε}.
13 — Fibonacci 1,2,3,5,8,13.
AB — Distributivity makes A = B.
- C: Second from the end.
- D: First symbol b.
B — Two a’s with anything around them.
- A: More a’s can appear in the gaps.
- C: They need not be adjacent.
- D: Three a’s also match.