Language Theory Basics

Strings

A symbol is a primitive unit of data representation.

An alphabet is a finite set of symbols.

Example: Σ = {a, b, c}.

A string is a finite sequence of symbols over some alphabet.

Examples: w = abbcbabb, x = b, y = aaa.

The length of a string is the number of symbol occurrences in the string.

Example: if w = abbac, then |w| = 5.

The empty string, denoted ε, is the (unique) string of length 0.

The concatenation of two strings x and y is the string obtained by appending y at the end of x. Also, we define w⁰ = ε. w¹ = w. w² = ww. w^k+1 = ww^k.

Example: if x = abb and y = ca then xy = abbca.

Example: wε = εw = w.

Example: (abc)⁴ = abcabcabcabc.

The reversal w^R of a string w is the string formed by reversing w; formally ε^R = ε and (σw)^R = w^Rσ for some symbol σ

x is a substring of y iff ∃v ∃w. y = vxw.

Languages

A language is a set of strings over some alphabet.

The concatenation of two languages L₁ and L₂ is L₁L₂ = {xy | x ∈ L₁ ∧ y ∈ L₂}. Also, we define L⁰ = {ε}, L¹ = L, L² = LL, ... L^k+1 = LL^k.

The Kleene Closure of L is L^* = L⁰ ∪ L¹ ∪ L² ∪ ... = {w₁w₂...w_k | w_i ∈ L ∧ k ≥ 0}.

The Positive Closure of L is L⁺ = L¹ ∪ L² ∪ L³ ∪ ... = {w₁w₂...w_k | w_i ∈ L ∧ k > 0}.

If Σ is an alphabet then Σ is also a language over Σ. So is Σ^*. Σ^* is important: it is the set of all strings over Σ. So for any language L over Σ, L ⊆ Σ^*. Also important is that &Sigma^* is countable.

Examples:

Σ = {a,b}

Σ^* = {ε,a,b,aa,ab,ba,bb,aaa,aab,aba,...}

L₁ = {ba, b}

L₂ = {abb, bb}

L₁^* = {ε,ba,b,baba,bab,bba,bb,...}

L₁⁺ = {ba,b,baba,bab,bba,bb,...}

L₁L₂ = {baabb, babb, bbb}

Some Language Theorems

Let Σ be an alphabet and A, B, C, and D be languages over Σ (i.e. subsets of &Sigma^*).

A∅ = ∅A = ∅

A{ε} = {ε}A = A

(AB)C = A(BC)

(A ⊆ B) ∧ (C ⊆ D) ⇒ AC ⊆ BD

A(B ∪ C) = AB ∪ AC

(B ∪ C)A = BA ∪ CA

A(B ∩ C) ⊆ AB ∩ AC

(B ∩ C)A ⊆ BA ∩ CA

A^* = A⁺ ∪ {ε}

Aⁿ ⊆ A^*, n ≥ 0

Aⁿ ⊆ A⁺, n ≥ 1

A ⊆ AB^*

A ⊆ B^*A

A ⊆ B ⇒ A^* ⊆ B^*

A ⊆ B ⇒ A⁺ ⊆ B⁺

AA^* = A^*A = A⁺

{ε} ∈ A iff A⁺ = A^*

(A^*)^* = A^*A^* = A^*

(A^*)⁺ = (A⁺)^* = A^*

A^*A⁺ = A⁺A^* = A^*

(A^*B^*)^* = (A ∪ B)^* = (A^* ∪ B^*)^*

(C = AC ∪ B) ⇒ (C = A^*B)

Language Theory Basics

Strings

Languages

Some Language Theorems

Types of Languages

Finite Languages

Regular Languages

Context Free Languages

Context Sensitive Languages

Recursive Languages

Recursively Enumerable Languages

Non-Recursively Enumerable Languages