Formal Languages

Definition

A formal language (or just language) over alphabet $\Sigma$ is any subset $L \subseteq \Sigma^*$.

Intuition

A language is specified by giving the “words in the dictionary” - the strings that belong to it.

Examples

Language	Alphabet	Description
$\emptyset$	any	Empty language (no strings)
$\{\varepsilon\}$	any	Language containing only the empty string
$\Sigma^*$	$\Sigma$	All strings over $\Sigma$
$\{a^n b^n : n \geq 0\}$	$\{a, b\}$	Equal numbers of $a$‘s and $b$‘s
${w :	w	\text{ even}}$

Operations on Languages

Union

$L_1 \cup L_2 = \{w : w \in L_1 \lor w \in L_2\}$

Intersection

$L_1 \cap L_2 = \{w : w \in L_1 \land w \in L_2\}$

Complement

$L^c = \Sigma^* \setminus L = \{w \in \Sigma^* : w \notin L\}$

Concatenation of Languages

Definition

$L_1 \cdot L_2 = \{uv : u \in L_1 \land v \in L_2\}$

Properties

• Identity: $L \cdot \{\varepsilon\} = L = \{\varepsilon\} \cdot L$
• Associativity: $(L_1 \cdot L_2) \cdot L_3 = L_1 \cdot (L_2 \cdot L_3)$
• Distributive over union: $L_1 \cdot (L_2 \cup L_3) = (L_1 \cdot L_2) \cup (L_1 \cdot L_3)$

Special Cases

• $L \cdot \emptyset = \emptyset = \emptyset \cdot L$
• $\{\varepsilon\} \cdot L = L$

Kleene Star

Definition

The Kleene star of language $L$ is:

$L^* = \bigcup_{n \geq 0} L^n = \{\varepsilon\} \cup L \cup L^2 \cup L^3 \cup \cdots$

where $L^n = \underbrace{L \cdot L \cdot \ldots \cdot L}_{n \text{ times}}$.

Alternative Definition

$L^*$ is the smallest language containing $\{\varepsilon\}$ and $L$, closed under concatenation.

Examples

• $\{a\}^* = \{\varepsilon, a, aa, aaa, \ldots\}$
• $\{a, b\}^* = \Sigma^*$ if $\Sigma = \{a, b\}$
• $\emptyset^* = \{\varepsilon\}$ (only the empty string)
• $\{\varepsilon\}^* = \{\varepsilon\}$

Kleene Plus

$L^+ = L \cdot L^* = L^* \setminus \{\varepsilon\} = \bigcup_{n \geq 1} L^n$

Language Properties

Finite vs Infinite Languages

A language is finite if $|L| < \infty$, otherwise infinite.

Examples:

• $\{a, aa, aaa\}$: finite (3 elements)
• $\{a^n : n \geq 0\}$: infinite

Decidable Languages

A language $L$ is decidable if there is an algorithm that determines whether any $w \in \Sigma^*$ belongs to $L$.

Closure Properties

Languages are closed under:

Operation	Result
Union	$L_1 \cup L_2$
Intersection	$L_1 \cap L_2$
Complement	$L^c$
Concatenation	$L_1 \cdot L_2$
Kleene star	$L^*$

Special Languages

The Empty Language

$L = \emptyset$: contains no strings.

Note: $\emptyset \neq \{\varepsilon\}$.

The Universal Language

$L = \Sigma^*$: contains all strings.

Singleton Languages

$L = \{w\}$: contains exactly one string.

---

Summary

• A formal language is any subset $L \subseteq \Sigma^*$
• Operations: union, intersection, complement, concatenation, Kleene star
• $L^* = \bigcup_{n \geq 0} L^n$ is the Kleene closure
• Languages form a Boolean algebra under $\cup$, $\cap$, complement