Exercises — Alphabet, string, language — formal definitions

$|w|$ counts symbol-positions. The string $011010$ has six positions written left to right, so $|011010|=6$. The empty string has no positions, so $|\epsilon |=0$.

(a) Yes. ${\Sigma }^{\ast }={\bigcup }_{k\ge 0}{\Sigma }^k$ and the $k=0$ layer ${\Sigma }^0=\{\epsilon \}$ is included, so $\epsilon \in {\Sigma }^{\ast }$. (b) No. $\varnothing$ is the language holding zero strings — nothing is inside it, not even $\epsilon$. (c) No. $\{\epsilon \}$ holds exactly one string (the blank word), so $|\{\epsilon \}|=1\ne 0=|\varnothing |$. Different floors: $\epsilon$ is a string, $\{\epsilon \}$ and $\varnothing$ are languages.

$|{\Sigma }^3|=|\Sigma {|}^3=2^3=8$. Two examples: $000$ and $101$.

Why sum the layers? "Length at most 3" is the union ${\Sigma }^0\cup {\Sigma }^1\cup {\Sigma }^2\cup {\Sigma }^3$, and these layers are disjoint (a string has exactly one length), so counts add: $2^0+2^1+2^2+2^3=1+2+4+8=15.$

Rule: $L_1{L}_2=\{xy:x\in L_1,y\in L_2\}$ — glue every left piece to every right piece.

• $a\cdot b=ab$
• $a\cdot \epsilon =a$
• $ab\cdot b=abb$
• $ab\cdot \epsilon =ab$

Collect as a set (drop the duplicate $ab$): $L_1{L}_2=\{a,ab,abb\}$. So $|L_1{L}_2|=3$.

$w^n=w^{n-1}w$, so $w^3=www=010101=010101$. Length multiplies: $|w^3|=3\cdot |w|=3\cdot 2=6$. ✔

Reversal is defined by ${\epsilon }^R=\epsilon$ and $(xa{)}^R=a(x^R)$. Induct on length. Base: $|{\epsilon }^R|=|\epsilon |=0=|\epsilon |$. ✔ Step: assume $|x^R|=|x|$. Then for $w=xa$, $|w^R|=|(xa{)}^R|=|a{x}^R|=1+|x^R|=1+|x|=|xa|=|w|.$ Reversal only re-orders positions — a bijection on positions — so the count can't change. Check: $(001{)}^R=100$, and $|100|=3=|001|$. ✔

(a) $\varnothing L=\{xy:x\in \varnothing ,y\in L\}$. There is no $x$ to pick, so no pair exists: $\varnothing L=\varnothing$. (b) $\{\epsilon \}L=\{\epsilon y:y\in L\}=\{y:y\in L\}=L$, since $\epsilon y=y$. So $\{\epsilon \}L=\{0,1\}=L$. (c) ${\varnothing }^{\ast }={\bigcup }_{k\ge 0}{\varnothing }^k$. By definition ${\varnothing }^0=\{\epsilon \}$ (always included), and ${\varnothing }^k=\varnothing$ for $k\ge 1$. Union: ${\varnothing }^{\ast }=\{\epsilon \}$.

$|\epsilon |=0$ and $0$ is even, so $\epsilon \in L$. $L$ is infinite — it contains a string of every even length $0,2,4,\dots$, so there is never a "last" one. Length-$4$ strings: every string of length $4$ has even length, so all of ${\Sigma }^4$ qualifies: $|{\Sigma }^4|=2^4=16$.

Fix the constrained positions, count the free ones. A length-5 string has positions $p_1{p}_2{p}_3{p}_4{p}_5$. The problem forces $p_1=1$ and $p_5=0$. The remaining $p_2,p_3,p_4$ are free, each with $2$ choices. By the multiplication rule: $|L|=2\times 2\times 2=2^3=8.$

$L^k$ concatenates $k$ picks, each pick being one symbol from $\{0,1\}$. A row of $k$ freely-chosen symbols is exactly a length-$k$ string, so $L^k={\Sigma }^k$. Therefore $|L^3|=|{\Sigma }^3|=2^3=8$.

$L^{\ast }={\bigcup }_{k\ge 0}{L}^k$ with $L^0=\{\epsilon \}$, $L^k=(01{)}^k$.

• $k=0$: $\epsilon$ (length 0)
• $k=1$: $01$ (length 2)
• $k=2$: $0101$ (length 4)

Length $\le 4$: $\{\epsilon ,01,0101\}$. Since $L$ has one string, each power has one string: $|L^2|=1$.

Sum the disjoint layers, a finite geometric series: $N(n)={\sum }_{k=0}^n{2}^k=2^{n+1}-1.$ (Geometric-series identity ${\sum }_{k=0}^n{r}^k=\frac{r^{n+1}-1}{r-1}$ with $r=2$.) At $n=4$: $N(4)=2^5-1=31$.

Use shortlex (canonical) order: list strings by length first, and within a length use ordinary alphabetical order ($0$ before $1$). This produces a single infinite list with no gaps and no repeats, so numbering it $0,1,2,\dots$ is a bijection with the naturals — that is the definition of countably infinite. The list begins ($\Sigma =\{0,1\}$): $\underset{0}{\underbrace{\epsilon }},\underset{1}{\underbrace{0}},\underset{2}{\underbrace{1}},\underset{3}{\underbrace{00}},\underset{4}{\underbrace{01}},\underset{5}{\underbrace{10}},\underset{6}{\underbrace{11}},\underset{7}{\underbrace{000}},\dots$ So $\epsilon$ sits at position $0$ and $10$ at position $5$. Every finite string appears at some finite position because it has a finite length $k$ and only finitely many ($2^k$) strings share that length ahead of it. See the ordering below.

A language is any subset of ${\Sigma }^{\ast }$, so the set of all languages is the power set $2^{{\Sigma }^{\ast }}$. Cantor's theorem says the power set of an infinite set is strictly larger — uncountable. But every machine (DFA/NFA, regex, grammar, Turing machine) is itself a finite description, so there are only countably many machines. Countably many machines cannot cover uncountably many languages ⇒ some languages are recognised by no machine at all — they are undecidable. This mismatch is the seed of the limits and undecidability results that dominate the rest of the theory and separate the regular languages from everything bigger.

• $|\epsilon |=0$, and $0$ is even — $\epsilon$ obeys length-conditions like any string.
• $\varnothing (\text{size }0)\ne \{\epsilon \}(\text{size }1)\ne \epsilon (\text{a string})$.
• $|{\Sigma }^k|=|\Sigma {|}^k$; "at most $n$" sums to $2^{n+1}-1$ when $|\Sigma |=2$.
• Language concatenation returns a set — deduplicate before counting.
• ${\varnothing }^{\ast }=\{\epsilon \}$ because $L^0=\{\epsilon \}$ is always included.
• ${\Sigma }^{\ast }$ countable (finite strings, shortlex); $2^{{\Sigma }^{\ast }}$ uncountable (seed of undecidability).