Kody i szyfry

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ⁿ ∪ ...