Sets of Strings

Context: FIT1058_MOC · the sets used to encode data symbolically · built from an alphabet · generated by powers $A^k$ and the Kleene star $A^{\ast }$

Quick Revision

• 🎯 Objective: encode data as finite strings over an alphabet ➔ $A^k$ = length-$k$ strings, $A^{\ast }$ = all finite strings.
• 📦 Core Components: alphabet $A$ ➔ empty string $\epsilon$ ➔ $A^{\ast }={\bigcup }_k{A}^k$.
• ⚡ Key Constraint: $A^0=\{\epsilon \}\ne \varnothing$; $A^{\ast }$ is infinite; a language is a subset of $A^{\ast }$.

📝 Core

1. Strings over an Alphabet

• Alphabet ➔ a finite set $A$ of characters.
• String ➔ a finite sequence of characters from $A$; length = number of characters.
• Empty string ➔ $\epsilon$, length $0$.

2. Powers and Kleene Star

• Power ➔ $A^k$ = all length-$k$ strings, $|A^k|=|A{|}^k$.
• Kleene star ➔ $A^{\ast }={\bigcup }_{k=0}^{\infty }{A}^k$ = all finite strings.
• $A^1$ ➔ the alphabet itself.

3. Languages

• Language ➔ any subset of $A^{\ast }$ (e.g. valid words).
• Universal set ➔ $A^{\ast }$ is the natural $U$ for string problems.
• Everything digital ➔ words, integers, files, DNA are subsets of some $A^{\ast }$.

Key identities:

$A^0=\{\epsilon \},A^1=\{0,1\},A^3=\{000,001,010,011,100,101,110,111\}$ $A^{\ast }={\bigcup }_{k=0}^{\infty }{A}^k,|A^k|=|A{|}^k$

⚖️ Core Decision Matrix

Object	Meaning	Size
$A^0$	$\{\epsilon \}$	1
$A^k$	length-$k$ strings	$|A{|}^k$
$A^{\ast }$	all finite strings	infinite (if $A\ne \varnothing$)
language	subset of $A^{\ast }$	varies

When It Flips: strings are ordered (ab≠ba), alphabets are not; a length-$k$ string is an element of $A^k=A\times \cdots \times A$ (Cartesian Product), and $A^{\ast }$ is the infinite union ${\bigcup }_k{A}^k$.

📊 Exam Execution Trace

Manual Execution Trace

$A=\{a,b\}$ by length:

Step / State	$k$	$A^k$	$|A^k|$
0 (Init)	—	—	—
1	0	$\{\epsilon \}$	1
2	1	$\{a,b\}$	2
3	2	$\{aa,ab,ba,bb\}$	4

⚠️ Common Mistakes

• 💡 $A^0=\{\epsilon \}\ne \varnothing$ ➔ $A^0$ has one element (the empty string), $|A^0|=1$; the empty set has none. A box containing one empty box is not empty.

🧠 Active Recall

Why is $A^0=\{\epsilon \}$ different from $\varnothing$, and what are their cardinalities?

• Hint: One element vs none.

Answer

• Short answer: $A^0=\{\epsilon \}$ has $|A^0|=1$; $\varnothing$ has $|\varnothing |=0$.
• Why: Contains something ➔ $\{\epsilon \}$ holds the empty string; $\varnothing$ holds nothing.

For $A=\{0,1\}$ list $A^3$, give $|A^k|$, and say why $A^{\ast }$ is infinite.

• Hint: No longest string.

Answer

• Short answer: $A^3$ = the 8 length-3 binary strings; $|A^k|=|A{|}^k$.
• Why: Every length ➔ $A^{\ast }={\bigcup }_{k\ge 0}{A}^k$ has no longest string when $A\ne \varnothing$.