Operations on languages

1. |∅| and |{ε}|?
   Stuck? Peek at 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.

   Read lesson 0.3.2

2. How many binary strings of length 4 have exactly one 1?
   Stuck? Peek at 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.

   Read lesson 0.3.2

3. If A − B is written with ∩ and complement, what is it?
   Stuck? Peek at 0.2.1 Sets

   • x ∈ A (element) vs X ⊆ A (subset). ∅ ⊆ every set. A = B ⇔ A ⊆ B and B ⊆ A.
   • A ∪ B, A ∩ B, A − B = A ∩ B̅, A̅ = U − A. De Morgan: (A∪B)̅ = A̅∩B̅, (A∩B)̅ = A̅∪B̅.
   • |A ∪ B| = |A| + |B| − |A ∩ B|. |A × B| = |A|·|B|. |P(A)| = 2^|A|.
   • |∅| = 0, |{∅}| = 1, P(∅) = {∅}.

   Read lesson 0.2.1

A website accepts a username followed by a digit. The set of valid usernames is one language, the set of digits another; the valid logins are “a username glued to a digit”. A log file is “any number of valid lines in a row”. Gluing and repeating are new operations that sets of numbers don’t have, but sets of strings do. They are exactly the operations regular expressions are made of.

Let L = {a, ab}. How many strings are in L·L = { xy : x ∈ L, y ∈ L }? (Careful — guess, then check for duplicates.)

Prediction check

Pairs: a·a = aa, a·ab = aab, ab·a = aba, ab·ab = abab. All different: 4. But with L = {a, aa}: a·aa = aaa and aa·a = aaa collide, so L·L = {aa, aaa, aaaa} has only 3. |L₁L₂| ≤ |L₁|·|L₂|, with equality only when no collisions occur.

Set operations still work

Languages are sets, so: L₁ ∪ L₂, L₁ ∩ L₂, L₁ − L₂, and the complement L̅ = Σ* − L (the universe is Σ*). Complement of “strings starting with a” over {a,b} is “strings not starting with a” = strings starting with b, plus ε. Never forget ε in complements.

Concatenation of languages

• L{ε} = {ε}L = L ({ε} is the identity).
• L∅ = ∅L = ∅ (nothing to pair with — ∅ is the “zero”).
• Not commutative: {a}{b} = {ab} but {b}{a} = {ba}.

Powers of a language

L⁰ = {ε}, L¹ = L, Lⁿ⁺¹ = LⁿL. Lⁿ = all strings made by gluing n strings from L. {a,b}ⁿ = Σⁿ. Note ∅⁰ = {ε} (by definition) but ∅ⁿ = ∅ for n ≥ 1.

Kleene star and plus

• ε ∈ L* always. ε ∈ L⁺ iff ε ∈ L.
• L⁺ = LL* = L*L. L* = L⁺ ∪ {ε}.
• ∅* = {ε}; {ε}* = {ε}; ∅⁺ = ∅.
• (L*)* = L*; L*L* = L*.
• If L contains at least one non-empty string, L* is infinite.

Example: {ab}* = {ε, ab, abab, ababab, …}. {a, b}* = Σ*. {aa}* = all strings of a’s with even length.

Reversal of a language

Lᴿ = { wᴿ | w ∈ L }. {ab, abc}ᴿ = {ba, cba}. (L₁L₂)ᴿ = L₂ᴿL₁ᴿ.

Counting strings of a given length in a language

• Positions argument: binary strings of length n with exactly r 1’s: C(n, r).
• Fixed parts: length-n binary strings starting with 01: 2ⁿ⁻² (the other n−2 positions are free).
• Inclusion–exclusion: start with a OR end with b (length n ≥ 2, over {a,b}): 2ⁿ⁻¹ + 2ⁿ⁻¹ − 2ⁿ⁻² .
• Complement counting: “contains at least one a” = all − “no a’s” = 2ⁿ − 1.

Putting it together

• Concatenation glues; L{ε} = L, L∅ = ∅; it is not commutative.
• Star = zero or more (always ε), plus = one or more; ∅* = {ε}* = {ε}.
• Count strings by fixing positions, choosing positions C(n,r), inclusion–exclusion, or complement.

L = {a, ab}
L⁰ = {ε}
L¹ = {a, ab}
L² = {aa, aab, aba, abab}
L* = {ε, a, ab, aa, aab, aba, abab, aaa, ...}

identity & zero table
 ┌──────────────┬───────────────┐
 │ L{ε} = L     │ L∅ = ∅        │
 │ ∅* = {ε}     │ {ε}* = {ε}    │
 │ ∅⁺ = ∅       │ ∅⁰ = {ε}      │
 │ L⁺ = LL*     │ L* = L⁺ ∪ {ε} │
 └──────────────┴───────────────┘

We have the full vocabulary: strings, languages, and operations on languages. One last idea completes Phase 0: every yes/no question is a language, so “solving a problem” means “telling which strings are in a set”.

1. MCQ

   Which equals ∅*?

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

   Over {0,1}, how many strings of length 8 contain at least one 0?

   Write your answer before opening the key.

3. MSQ

   Which are always true for any language L?

   1. L{ε} = L
   2. L∅ = L
   3. ε ∈ L*
   4. L⁺ = L* − {ε}
4. NAT

   L = {ab, ba}. How many strings are in L³?

   Write your answer before opening the key.

5. MCQ

   Over {a,b}, the complement of L = {w : w starts with a} is:

   1. {w : w starts with b}
   2. {w : w starts with b} ∪ {ε}
   3. {w : w ends with b}
   4. Σ⁺

• language union/intersection/complement (w.r.t. Σ*)
• concatenation L₁L₂
• language power Lⁿ, L⁰ = {ε}
• Kleene star L*
• Kleene plus L⁺
• reversal of a language Lᴿ
• counting strings of a given length

1. ∅* = ? and {ε}* = ?
   Reveal answer

   Both equal {ε}.
2. L∅ = ?
   Reveal answer

   ∅
3. Relation between L⁺ and L*?
   Reveal answer

   L⁺ = LL*; L* = L⁺ ∪ {ε}.
4. Strings of length n over {a,b} starting with a OR ending with b?
   Reveal answer

   2ⁿ⁻¹ + 2ⁿ⁻¹ − 2ⁿ⁻² (inclusion–exclusion).

• “At least one X” counts: total minus “no X”. Binary length n with at least one 1: 2ⁿ − 1.
• Star of a set of one-symbol strings: {a, aa}* = {a}* because every length is reachable with 1s.