Formal Languages (Alphabets, Words, Languages)

Context: FIT2014_MOC · computation is done with strings of symbols, so the whole unit is built on this vocabulary · foundation for regular languages, automata and grammars later

Quick Revision

• 🎯 Objective: alphabet $\Sigma$ (finite symbol set) ➔ word (finite string over $\Sigma$) ➔ language (a set of words over $\Sigma$).
• ⚡ Key Constraint: distinguish the empty language $\varnothing =\{\}$ from the language containing the empty word $\{\epsilon \}$ — the first has $0$ elements, the second has $1$.

📝 Core definitions

• Alphabet ➔ a finite set of symbols, denoted $\Sigma$; members are letters/characters. E.g. $\{a,b\}$, $\{0,1\}$, $\{0,\dots ,9\}$.
• Word ➔ a finite string of symbols; a word over $\Sigma$ draws all symbols from $\Sigma$. The empty word has length $0$, written $\epsilon$ (sometimes $\Lambda$).
• Language ➔ a set of words over $\Sigma$ — note a language is a set, not a string.
• Default convention ➔ unless stated otherwise, $\Sigma =\{a,b\}$.

🔢 Special languages & notation

• Empty language ➔ $\varnothing =\{\}$ — contains no words.
• Language of the empty word ➔ $\{\epsilon \}$ — contains exactly one word.
• Fixed length ➔ ${\Sigma }^k:=\{\text{all words over }\Sigma \text{ of length }k\}$, e.g. $\{a,b{\}}^2=\{aa,ab,ba,bb\}$.
• Universal language ➔ ${\Sigma }^{\ast }:=\{\text{all finite words over }\Sigma \}$.
• Repetition ➔ $x^k$ concatenates $k$ copies of $x$: $a^2=aa$, $a{b}^3=abbb$, $(ab{)}^3=ababab$. Note $x^0=\epsilon$ for any $x$ (so $(baa{)}^0=\epsilon$).

📚 Three worked example languages

Language	Definition	Members (sample)
EVEN-EVEN	each of $a,b$ occurs an even number of times	$\epsilon ,aa,bb,aaaa,aabb,abab,abba,baab,\dots$
DOUBLEWORD	$\{xx:x\in {\Sigma }^{\ast }\}$ — a word concatenated with itself	$\epsilon ,aa,bb,aaaa,abab,baba,bbbb,\dots$
PALINDROMES	reads the same forwards and backwards	$\epsilon ,a,b,aa,bb,aba,bab,abba,\dots$

• Remember $0$ is even ➔ $\epsilon \in$ EVEN-EVEN.
• $\epsilon \epsilon =\epsilon$ ➔ so $\epsilon \in$ DOUBLEWORD (take $x=\epsilon$).

🧮 Formal Proof Blueprint — $\text{DOUBLEWORD}\subseteq \text{EVEN-EVEN}$

Theorem. $\text{DOUBLEWORD}\subseteq \text{EVEN-EVEN}$.

Strategy (subset proof). To prove $A\subseteq B$: take a general member of $A$, name things, use the definitions, and derive membership of $B$.

Derivation.

$$\begin{array}{rl}\text{Let }w& \in \text{DOUBLEWORD}\\ \Rightarrow w& =xx\text{for some word }x\text{(definition of DOUBLEWORD)}\\ {\#}_a(w)& =2\times {\#}_a(x)\Rightarrow {\#}_a(w)\text{ is even}\\ {\#}_b(w)& =2\times {\#}_b(x)\Rightarrow {\#}_b(w)\text{ is even}\\ \Rightarrow w& \in \text{EVEN-EVEN}\end{array}$$

Q.E.D. $■$

• Why “proof by example” fails here ➔ listing members of DOUBLEWORD that happen to be in EVEN-EVEN is a non-proof; a universal claim needs an argument covering every case.
• The exception ➔ an existential theorem (“English has a palindrome”) is settled by one witness (rotator) — see Quantifiers (Existential and Universal).

⚠️ Common Mistakes

• 💡 $\varnothing \ne \{\epsilon \}$ ➔ the empty language contains nothing; $\{\epsilon \}$ contains one (empty) word. Sizes $0$ vs $1$.
• 💡 Language = set of words, word = string ➔ a language is not itself a string; conflating the two breaks every later definition.
• 💡 Proof by example is not a proof ➔ except when the theorem only asserts existence. Universal statements need a general argument (Proof Techniques).

🧠 Active Recall

Why is $\epsilon$ a member of both EVEN-EVEN and DOUBLEWORD?

Answer

• Short answer: $\epsilon$ contains $a$ zero times and $b$ zero times, and $0$ is even, so $\epsilon \in$ EVEN-EVEN. Taking $x=\epsilon$ gives $xx=\epsilon \epsilon =\epsilon$, so $\epsilon \in$ DOUBLEWORD.
• Why: Degenerate cases satisfy definitions ➔ the definitions quantify over counts and decompositions that are vacuously/trivially met at length $0$ — a standard exam trap.

Why does exhibiting many DOUBLEWORD members inside EVEN-EVEN fail to prove $\text{DOUBLEWORD}\subseteq \text{EVEN-EVEN}$?

Answer

• Short answer: the claim is universal (every member of DOUBLEWORD lies in EVEN-EVEN); examples cover finitely many cases while the language is infinite, so they only illustrate.
• Why: Arbitrary-element argument ➔ take a general $w=xx$ and show ${\#}_a(w)=2{\#}_a(x)$ and ${\#}_b(w)=2{\#}_b(x)$ are even; this reasoning applies to all cases at once.