Podręcznik

Zbiór wszystkich słów nad ustalonym alfabetem V oznaczamy symbolem V^* a dowolny niepusty podzbiór L tego zbioru nazywamy językiem. Do zbioru V^* zaliczamy również słowo puste (oznaczane na ogół symbolem ε). Słowo puste ma długość 0. Zbiór V^* jest oczywiście nieskończony ale przeliczalny, mamy bowiem

V^* = {ε} ∪ V ∪ V² ∪ ... ∪ Vⁿ ∪ ...

W zbiorze V^* definiujemy działanie dwuargumentowe $\circ$ V^* × V^* → V^* tzw. konkatenację (ang. concatenation). Jeśli α, β ∈ V^* i α = a₁a₂...a_n β = b₁b₂...b_n to z definicji mamy

a $\circ$ b = a₁a₂...a_n $\circ$ b₁b₂...b_n $\overset{df}=$  a₁a₂...a_nb₁b₂...b_n

Jak widać konkatenacja jest zestawianiem słów np. ala konkatenowane z makota daje alamakota, podobnie kot z let daje kotlet.

Jak łatwo sprawdzić działanie konkatenacji jest łączne, tzn. dla każdego  α, β, γ ∈ V^* mamy (α $\circ$ β) $\circ$ γ = α $\circ$ (β $\circ$ γ). Mamy ponadto dla każdego α ∈ V^*; α $\circ$ ε = ε $\circ$ α = α  zatem słowo puste ε jest jedynką działania $\circ$: V^* × V^* → V^*. Inaczej mówiąc konkatenacja ze słowem pustym dowolnego słowa α ∈ V^* nie zmienia tego słowa. Zbiór ∈ V^* z działaniem konkatenacji $\circ$: V^* × V^* → V jest więc monoidem (czyli półgrupą z jednością). 

Widać natychmiast, że konkatenacja na ogół nie jest działaniem przemiennym w V^*, ale zawsze jest działaniem łącznym, tzn. na ogół x $\cdot$ y ≠ y $\cdot$ x  dla x, y ∈ V^*, ale zawsze tzn. dla każdego x, y, z ∈ V^*, mamy:

(x $\cdot$ y)  $\cdot$ z  = x $\cdot$ (y  $\cdot$ z)

Język to dowolny podzbiór zbioru V^*. Podzbiór ten można definiować na wiele sposobów np. za pomocą wyrażeń regularnych, notacją Backusa-Naura, gramatyką, automatem skończonym itd.. Wszystkie te sposoby poznamy w dalszym ciągu. Istnieje również wiele typów języków m.in. języki regularne, języki bezkontekstowe itd.

Złożeniem dwóch języków K i L, gdzie K, L ⊂ V^* nazywamy język

KL $\overset{df}{=}$ { x, y ∈ <em>V^*</em>;<em> </em>x, <em>y</em> ∈ <em>K</em> oraz <em>y</em> ∈ <em>L</em>}

Potęga języka. Potęgę L^* języka definiujemy indukcyjnie następująco

L⁰ $\overset{df}{=}$ {ε}, L¹ $\overset{df}{=}$ L,  L² $\overset{df}{=}$ LL, Lⁿ⁺¹ $\overset{df}{=}$ LLⁿ, ... 

Potęga liter. Potęgę liter definiujemy indukcyjnie następująco. Niech a będzie dowolną ustaloną literą a ∈ V^* wówczas a⁰ $\overset{df}{=}$ {ε}, a¹ $\overset{df}{=}$ a, a² $\overset{df}{=}$ aa, ..., aⁿ⁺¹ $\overset{df}{=}$ aaⁿ, ... 

Potęga słów. Potęgę słów definiujemy indukcyjnie następująco. Niech w będzie dowolnym ustalonym słowem, w ∈ V^*, wówczas w⁰ $\overset{df}{=}$ {ε}, w¹ $\overset{df}{=}$ w, w² $\overset{df}{=}$ ww, ..., wⁿ⁺¹ $\overset{df}{=}$ wwⁿ, ... 

Domknięcie języka (gwiazdeczka Kleen'a) L^*. Niech V będzie ustalonym alfabetem a L językiem L ⊂ V^*. Domknięciem języka L nazywamy zbiór L^* ⊂ V^*, gdzie

L^{* $\overset{df}{=}$} L⁰ ∪ L¹ ∪ L² ∪ ...,  ∪ Lⁿ ∪ ...