Chapter recap
Σ is a finite alphabet; strings are finite sequences; ε has length 0; concatenation adds lengths; (xy)ᴿ = yᴿxᴿ; length-n strings have n+1 prefixes and suffixes. Σᵏ has |Σ|ᵏ strings; Σ* is all strings; Σ⁺ = Σ* − {ε}. A language is any subset of Σ*; ∅ (no strings) ≠ {ε} (one string). Language operations: ∪, ∩, complement (w.r.t. Σ*), concatenation, powers, star (zero or more), plus (one or more). ∅* = {ε}* = {ε}; L∅ = ∅. Every yes/no problem is a membership question for some language.
Merged rule card
From 0.3.1 Alphabets and strings
- Σ finite non-empty; string = finite sequence; |ε| = 0; εw = wε = w.
- |xy| = |x| + |y|; wⁿ repeats w; w⁰ = ε; (xy)ᴿ = yᴿxᴿ.
- Length n: n+1 prefixes, n+1 suffixes; ≤ n(n+1)/2 + 1 distinct substrings (equality iff all pieces distinct, e.g. all symbols distinct).
- Substring = contiguous; subsequence = may skip.
From 0.3.2 Σᵏ, Σ*, Σ⁺ and languages
- |Σᵏ| = |Σ|ᵏ; Σ⁰ = {ε}; Σ* = ⋃ Σᵏ (k ≥ 0); Σ⁺ = Σ* − {ε}.
- #strings of length ≤ n over k symbols = (kⁿ⁺¹ − 1)/(k − 1); binary: 2ⁿ⁺¹ − 1.
- Language = any subset of Σ*. ∅ (no strings) ≠ {ε} (one string). Exactly r of one symbol in length n (binary): C(n, r).
- Shortlex order lists every string at a finite position.
From 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.
From 0.3.4 Problems as languages
- Problem P ↔ language L_P = {⟨x⟩ : answer yes}. ⟨X⟩ = string encoding of X.
- Solving P = machine M with: M says yes on w ⇔ w ∈ L_P (membership).
- Always test ε against count conditions.
Practice questions
- NAT
Number of strings over {a,b,c} of length exactly 3 that contain no c?
Write your answer before opening the key.
- MCQ
Which language is infinite?
- {ε}*
- ∅*
- {a}*
- {a, b}²
- MSQ
Which equal {ε}?
- ∅*
- {ε}⁺
- ∅⁰
- Σ⁰
- NAT
Distinct substrings (including ε) of
aab?Write your answer before opening the key.
- MCQ
L₁ = {a, b}, L₂ = {ε, a}. |L₁L₂| = ?
- 2
- 3
- 4
- 6
- NAT
Over {0,1}, how many strings of length 7 begin with 1 and end with 0?
Write your answer before opening the key.
- MCQ
For L = {ab}, which string is in L* but not in L⁺?
- ab
- abab
- ε
- none
- MSQ
L = {w ∈ {a,b}* : w = wᴿ}. Which are in L?
- ε
- ab
- aba
- abba
Answer key
Reveal answers when you’re ready
- 8 — 2³.
- C — {a}* = {ε, a, aa, …}.
- A: = {ε}.
- B: = {ε}.
- D: 4 strings.
- ABCD — All four are {ε}: ∅*={ε}; {ε}⁺ = {ε}; any L⁰ = {ε}; Σ⁰ = {ε}.
- 6 — ε, a, b, aa, ab, aab.
- C — a, aa, b, ba — all distinct.
- A: Missing products.
- B: No collisions here.
- D: That would be 2×3.
- 32 — 5 free positions: 2⁵.
- C — ε comes from zero repetitions.
- A: In both.
- B: In both.
- D: ε is such a string.
- ACD — Palindromes, including ε.
- B: Reverse is ba.