Formal Languages

A formal language is just a set of strings. That's it. Nothing more mysterious.
The whole point is to distinguish "good" strings (members of the language, like
well-formed programs) from "bad" strings (non-members, like syntax errors).

Kleene star (Definition 7.1.7, notes p. 119): for an alphabet $\Sigma$:

This is the set of all strings over $\Sigma$, including $\epsilon$. So
$\Sigma^* = \{\epsilon\} \cup \Sigma \cup \Sigma^2 \cup \Sigma^3 \cup \dots$.

Kleene plus: $\Sigma^+ = \Sigma^* \setminus \{\epsilon\}$ — all nonempty strings.

Definition 7.1.9: A formal language over $\Sigma$ is a set $L \subseteq \Sigma^*$.

Operations on languages (Definition 7.1.13):
- Union $L_1 \cup L_2$, intersection $L_1 \cap L_2$, complement $\Sigma^* \setminus L$.
- Concatenation $L_1 L_2 = \{uw \mid u \in L_1, w \in L_2\}$.
- Power $L^n$: $n$-fold concatenation of $L$ with itself ($L^0 = \{\epsilon\}$).
- Kleene closure $L^* = \bigcup_{n \ge 0} L^n$.

Important sanity check: a formal language may be infinite (e.g. all strings
starting with $b$ followed by any number of $a$'s) — but the alphabet is finite.
The infinite-ness comes from repetition.

Why this matters in AI:
- The set of valid programs in Python is a formal language over Unicode.
- The set of valid logical formulas in propositional logic is a formal language
over $\{p, q, r, \neg, \land, \lor, (, )\}$.
- The set of grammatical English sentences is (approximately) a formal language.

Two more operations on languages over alphabet $\Sigma$:

Complement (Def 1.7): $\overline{L} := \Sigma^* \setminus L$. The set of all strings not in $L$.

Reflection / Reversal (Def 1.8): $L^R := \{ w^R \mid w \in L \}$, where $w^R$ is $w$ reversed.

Kleene plus (Def 1.7): $L^+ := L \cup L^2 \cup L^3 \cup \cdots$ — one or more concatenations (vs. Kleene star $\Sigma^*$ which includes zero).

Examples over $\Sigma = \{a, b\}$:
- $L = \{ab, ba\}$. $\overline{L} = \Sigma^* \setminus \{ab, ba\}$ — every string except ab and ba.
- $L^R = \{ba, ab\}$ — same set for this symmetric example.
- $L^+ = \{ab, ba, abab, abba, baab, baba, \ldots\}$ — concatenations of length $\geq 1$.