Alphabets and strings

1. In a directed graph, when are there infinitely many paths between two nodes?
   Stuck? Peek at 0.2.5 Directed graphs

   • Directed graph (V, E ⊆ V×V); self-loop; in/out-degree; labelled edges spell words along paths.
   • Path length = #edges. Cycle = path returning to start. Self-loop = cycle of length 1.
   • Reachable set: grow from u until nothing new (BFS). Shortest path in n-node graph ≤ n−1 edges.
   • Infinitely many u→v paths ⇔ some cycle lies on a u→v route.

   Read lesson 0.2.5

2. A 6-mode machine reads 6 symbols. Must some mode repeat?
   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

3. How many subsets does a 4-element set have?
   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 reads a finite sequence of symbols. A barcode is a sequence over {thick, thin}. A binary number is a sequence over {0, 1}. Your code is a sequence over the keyboard’s characters. To talk precisely about “inputs”, we name the symbols, the sequences, and the basic things you do with them: measure, join, reverse, cut.

The word gate has 4 letters. How many different prefixes does it have (beginnings, including the empty beginning and the whole word)?

Prediction check

Answer: 5: (empty), g, ga, gat, gate. A string of length n always has n + 1 prefixes.

Alphabet and string

Length and the empty string

The length |w| is the number of symbols: |abba| = 4. The empty string ε (epsilon) has no symbols: |ε| = 0. It is a real string — the input “nothing at all”.

|w|ₐ counts occurrences of symbol a: |abba|ₐ = 2, |abba|_b = 2.

Concatenation

Joining strings: if x = ab and y = ba, then xy = abba and yx = baab. |xy| = |x| + |y|.

• Order matters: xy ≠ yx in general.
• Grouping doesn’t: (xy)z = x(yz).
• ε is the identity: εw = wε = w.

Powers: w⁰ = ε, w¹ = w, wⁿ⁺¹ = wⁿw. So (ab)³ = ababab, a³ = aaa. Notation aⁿ means “a repeated n times”, and aⁿbⁿ means n a’s followed by n b’s (like aaabbb for n = 3).

Reversal

wᴿ is w written backwards: (abb)ᴿ = bba, εᴿ = ε. Rule: (xy)ᴿ = yᴿxᴿ (reverse, and swap the order — like taking off socks and shoes). A palindrome is a string with w = wᴿ: abba, aba, a, ε.

Prefix, suffix, substring

• Prefix of w: any x with w = xy for some y. (A beginning.)
• Suffix: any y with w = xy. (An ending.)
• Substring: any v with w = xvy. (A contiguous middle piece.)
• “Proper” prefix/suffix: not the whole string w. ε is a prefix, suffix and substring of every string.

Counts for |w| = n: prefixes n + 1; suffixes n + 1; proper prefixes n. Substrings: at most n(n+1)/2 non-empty ones plus ε — exactly that when all symbols are distinct; fewer when pieces repeat.

A subsequence (not the same thing!) keeps the order but may skip symbols: ac is a subsequence of abc but not a substring.

Putting it together

• A string is a finite sequence over a finite alphabet; ε has length 0 and is the identity for gluing.
• Concatenation adds lengths and is not commutative; (xy)ᴿ = yᴿxᴿ.
• Length n: n+1 prefixes, n+1 suffixes, at most n(n+1)/2 + 1 distinct substrings.

w = a b c a        |w| = 4

prefixes:  ε  a  ab  abc  abca                 (n+1 = 5)
suffixes:  ε  a  ca  bca  abca                 (n+1 = 5)

substrings by length (all positions):
 len 1:  a  b  c  a        → distinct: a, b, c          (3)
 len 2:  ab bc ca          → 3
 len 3:  abc bca           → 2
 len 4:  abca              → 1
 + ε                        → total distinct = 3+3+2+1+1 = 10
 (formula n(n+1)/2 + 1 = 11 would hold if no piece repeated; "a" repeats once)

reversal: (abca)ᴿ = acba        (xy)ᴿ = yᴿ xᴿ

We can now handle single strings. Machines, though, accept whole collections of strings. Next lesson combines strings with sets: the set of all strings, and the idea of a language.

1. NAT

   How many prefixes (including ε and the string itself) does a string of length 7 have?

   Write your answer before opening the key.

2. MCQ

   Which is always true for strings x, y?

   1. xy = yx
   2. (xy)ᴿ = xᴿyᴿ
   3. (xy)ᴿ = yᴿxᴿ
   4. |xy| = |x|·|y|
3. NAT

   Number of distinct non-empty substrings of banana?

   Write your answer before opening the key.

4. MSQ

   Let w = abc. Which are substrings of w?

   1. ε
   2. ac
   3. bc
   4. abc
5. MCQ

   What is |(ab)³ε|?

   1. 3
   2. 6
   3. 7
   4. 9

• alphabet Σ
• string (word)
• length |w|, |w|ₐ
• empty string ε
• concatenation xy
• string power wⁿ, aⁿbⁿ notation
• reversal wᴿ
• palindrome
• prefix, suffix, substring, proper
• subsequence

1. |ε| = ?
   Reveal answer

   0
2. (xy)ᴿ = ?
   Reveal answer

   yᴿ xᴿ
3. Number of prefixes of a length-n string?
   Reveal answer

   n + 1
4. Max distinct substrings (incl. ε) of a length-n string?
   Reveal answer

   n(n+1)/2 + 1 (when no piece repeats)
5. Substring vs subsequence?
   Reveal answer

   Substring is contiguous; a subsequence may skip symbols.