Σᵏ, Σ*, Σ⁺ and languages

1. How many suffixes does a string of length 5 have?
   Stuck? Peek at 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.

   Read lesson 0.3.1

2. What is (abc)ᴿ?
   Stuck? Peek at 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.

   Read lesson 0.3.1

3. Is ∅ ⊆ every set?
   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 machine says yes to some inputs and no to others. The collection of all inputs it says yes to is a set of strings. That set is the single most important object in TOC: it is called a language. “What does this machine do?” becomes “what language does it accept?”.

Over the alphabet {a, b}, how many strings have length exactly 3? And how many have length at most 3?

Prediction check

Length exactly 3: 2³ = 8 (each of 3 positions is a or b). At most 3: lengths 0,1,2,3 → 1 + 2 + 4 + 8 = 15 (don’t forget ε, the single string of length 0).

Σᵏ — all strings of one length

Σᵏ = the set of all strings over Σ of length exactly k. |Σᵏ| = |Σ|ᵏ. Σ⁰ = {ε} (one string, the empty one — so |Σ⁰| = 1, not 0).

Σ* and Σ⁺

Σ* is infinite, but every individual string in it is finite. This is the universe we work in from now on.

Strings of length ≤ n over k symbols: 1 + k + k² + … + kⁿ = (kⁿ⁺¹ − 1)/(k − 1). For k = 2: 2ⁿ⁺¹ − 1.

Language

Examples over Σ = {a, b}:

• L₁ = {a, ab, abb} — finite (3 strings).
• L₂ = {w | w starts with a} — infinite.
• L₃ = {aⁿbⁿ | n ≥ 0} = {ε, ab, aabb, aaabbb, …} — infinite.
• Σ* itself, and Σ⁺.

∅ versus {ε}

Two tiny languages that GATE loves to confuse:

• ∅ — the empty language. It contains no strings at all. |∅| = 0. A machine that says no to everything accepts ∅.
• {ε} — contains exactly one string, the empty string. |{ε}| = 1. A machine that says yes only to the empty input accepts {ε}.

Memorize: ∅ is an empty box; {ε} is a box with one blank sheet of paper in it.

Ordering strings: shortlex

To list Σ* one by one, use shortlex (canonical) order: shorter strings first; equal lengths in dictionary order. Over {a,b}: ε, a, b, aa, ab, ba, bb, aaa, … Every string appears at a finite position. (Plain dictionary order would never get past a, aa, aaa, … — b would never appear.)

Putting it together

• |Σᵏ| = |Σ|ᵏ, Σ⁰ = {ε}; Σ* is all strings, Σ⁺ = Σ* − {ε}.
• A language is any set of strings — any subset of Σ*.
• ∅ (no strings) and {ε} (one string) are different; check ε in every counting question.

Σ = {a,b}

 Σ⁰ = {ε}                          |Σ⁰| = 1
 Σ¹ = {a, b}                       |Σ¹| = 2
 Σ² = {aa, ab, ba, bb}             |Σ²| = 4
 Σ³ = {aaa,aab,aba,abb,baa,bab,bba,bbb}   |Σ³| = 8
 ─────────────────────────────────────────────
 Σ* = Σ⁰ ∪ Σ¹ ∪ Σ² ∪ ...   (infinite)      Σ⁺ = Σ* − {ε}

 ∅      = { }        no strings          |∅|   = 0
 {ε}    = { ε }      one empty string    |{ε}| = 1
 Σ*  ⊇  L  ⊇ ∅      every language sits between ∅ and Σ*

A language is a set, so we can union, intersect and complement languages. But strings can also be glued together, so languages get extra operations: concatenation and the star. Those are next — and they are the building blocks of regular expressions in Phase 2.

1. NAT

   Over Σ = {a, b, c}, how many strings have length at most 2?

   Write your answer before opening the key.

2. MCQ

   Which is true?

   1. ∅ = {ε}
   2. |{ε}| = 0
   3. Σ⁰ = {ε}
   4. ε ∈ Σ⁺
3. MSQ

   Over Σ = {0,1}, which sets are languages over Σ?

   1. ∅
   2. {ε}
   3. Σ*
   4. {0, 01, 2}
4. NAT

   Over {a,b}, how many strings of length 6 contain exactly three b’s?

   Write your answer before opening the key.

5. MCQ

   In shortlex order over {a,b}, which string comes 6th (ε is 1st)?

   1. ab
   2. ba
   3. aa
   4. bb

• Σᵏ (strings of length k)
• Σ* (all strings)
• Σ⁺ (non-empty strings)
• language L ⊆ Σ*
• finite / infinite language
• empty language ∅ vs {ε}
• shortlex order

1. ∅ vs {ε}?
   Reveal answer

   ∅ has no strings (size 0); {ε} has one string, the empty string (size 1).
2. Σ⁺ in terms of Σ*?
   Reveal answer

   Σ⁺ = Σ* − {ε}
3. Number of binary strings of length ≤ n?
   Reveal answer

   2ⁿ⁺¹ − 1
4. What is a language?
   Reveal answer

   Any set of strings over Σ, i.e. any subset of Σ*.