Problems as languages

1. Is ε in L⁺ when ε ∉ L?
   Stuck? Peek at 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.

   Read lesson 0.3.3

2. Over {a,b}, how many strings of length ≤ 3?
   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. What does the pigeonhole principle guarantee for an n-mode machine reading n symbols?
   Stuck? Peek at 0.2.4 Pigeonhole principle

   • n + 1 objects in n boxes ⇒ some box has ≥ 2.
   • N objects in k boxes ⇒ some box has ≥ ⌈N/k⌉. To force m in a box: (m−1)k + 1 objects.
   • Machine with n modes, input length ≥ n ⇒ some mode repeats ⇒ a loop in the input.

   Read lesson 0.2.4

“Is 91 a prime number?” sounds like a question about numbers, not strings. But a computer only ever sees strings — 91 arrives as the characters 1011011 in binary. So the question becomes: is the string 1011011 in the set of strings that encode primes? Every yes/no problem turns into a membership question about a language. This is the bridge that makes TOC work.

The problem “is this binary number even?” is the same as membership in which language over {0,1}? Describe it by a simple property of the string.

Prediction check

A binary number is even exactly when its last bit is 0. So the language is {w ∈ {0,1}⁺ | w ends with 0}. A deep-sounding arithmetic question became a one-glance property of the string.

Encoding

To feed any object to a machine, write it as a string: a number in binary, a list as symbols separated by commas, a graph as a list of edges, even a whole program as its source text. We write ⟨X⟩ for “the string that encodes X”.

Problem = language

This is called the membership problem: given a string w, is w ∈ L? “The machine accepts L” means: it says yes on every w ∈ L and does not say yes on any w ∉ L.

Examples

• PALINDROME = { w ∈ {a,b}* | w = wᴿ }.
• BALANCED = strings of ( and ) where brackets match properly.
• EQUAL = { w ∈ {a,b}* | |w|ₐ = |w|_b }.
• DIV3 = binary strings whose value is divisible by 3.

From Lesson 0.1.1 you already know which of these feel “finite-memory”: DIV3 only needs the remainder (3 possibilities). BALANCED and EQUAL need an unbounded count. PALINDROME needs to remember the whole first half. Phases 1–3 make these intuitions precise.

The roadmap from here

Each phase introduces a machine with more memory and asks: which languages can it accept?

1. Finite-memory machines (Phase 1–2).
2. Machines with a pile of plates (Phase 3).
3. Machines with an endless notebook (Phase 4).
4. Languages no machine can handle (Phase 5).

Putting it together

• Any object can be encoded as a string ⟨X⟩.
• A yes/no problem is the language of its yes-instances; solving it = answering membership.
• Which machine can solve it depends on the memory needed — the rest of the course.

   problem                       language (set of yes-strings)
 ┌──────────────────────┐        ┌──────────────────────────────────┐
 │ is n even?           │  ───►  │ { w ∈ {0,1}⁺ : w ends in 0 }     │
 │ is it a palindrome?  │  ───►  │ { w : w = wᴿ }                   │
 │ brackets balanced?   │  ───►  │ { (), (()), ()(), ... , ε }      │
 └──────────────────────┘        └──────────────────────────────────┘
      solve problem  ≡  build a machine M with  "M says yes on w"  ⇔  w ∈ L

Phase 0 is complete. You know the objects (strings, languages) and the tools (sets, functions, equivalence classes, proofs, pigeonhole, graphs). Phase 1 builds the first real machine: one with a fixed, finite set of modes — and gives those modes their proper name.

1. MCQ

   The problem “is the binary number divisible by 2?” corresponds to which language over {0,1}?

   1. strings starting with 0
   2. strings ending with 0
   3. strings with even length
   4. strings with an even number of 1s
2. MSQ

   L = { w ∈ {a,b}* : |w|ₐ = |w|_b }. Which strings are in L?

   1. ε
   2. abba
   3. aab
   4. baab
3. NAT

   How many strings of length 4 over {a,b} are in L = { w : |w|ₐ = |w|_b }?

   Write your answer before opening the key.

4. MCQ

   “Machine M accepts language L” means:

   1. M says yes to some strings of L
   2. M says yes to exactly the strings of L
   3. M says no to all strings outside L only
   4. M runs forever on strings of L

• encoding ⟨X⟩
• problem as a language L_P
• membership problem (is w ∈ L?)
• machine accepts a language (exactly the strings of L)

1. What does “M accepts L” mean?
   Reveal answer

   M says yes on every string in L and on no string outside L.
2. Binary numbers divisible by 2 as a language?
   Reveal answer

   Strings ending in 0.
3. Membership problem?
   Reveal answer

   Given w, decide whether w ∈ L.