Читать книгу Wprowadzenie do teorii obliczeń - Michael Sipser - Страница 23

Słowa, czyli ciągi znaków, stanowią fundamentalne cegiełki informatyki. Alfabet, nad którym definiowane są słowa, może się zmieniać w zależności od zastosowań. Dla naszych celów alfabet definiujemy jako niepusty skończony zbiór. Elementy tego zbioru są symbolami alfabetu. Zazwyczaj będziemy używać wielkich liter greckich S i G do oznaczania alfabetów oraz małych liter czcionki o stałej szerokości dla symboli alfabetu. Poniżej pokazano kilka przykładów alfabetów.

Σ₁ = {0, 1}

Σ₂ = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}

Γ = {0, 1, x, y, z}

Słowem nad alfabetem (także ciągiem nad alfabetem) jest skończony ciąg symboli z tego alfabetu, zazwyczaj wypisanych jeden po drugim bez odstępów i przecinków. Jeśli Σ₁ = {0,1}, wówczas 01001 jest słowem nad Σ₁. Jeśli Σ₂ = {a, b, c, … , z}, wtedy abracadabra jest słowem nad Σ₂. Jeżeli w jest słowem nad Σ, długość w, zapisywana jako |w|, jest liczbą zawartych w nim symboli. Słowo o długości zero nazywane jest pustym słowem i zapisywane jako ε. Słowo puste odgrywa rolę analogiczną do 0 w systemie liczbowym. Jeśli słowo w ma długość n, to możemy zapisać ją jako w = w₁w₂ … ·w_n, gdzie każdy w_i ∈ Σ. Odwrócenie słowa w, zapisywane jako wR, jest słowem uzyskiwanym z w przez zapisanie go w odwrotnej kolejności (czyli w_nw_n−1 …·w₁). Słowo z jest podsłowem w, jeśli jest spójnym podciągiem słowa w. Na przykład cad jest podsłowem słowa abracadabra.

Jeśli mamy słowo x o długości m oraz słowo y o długości n, to konkatenacją x i y, zapisywaną xy, jest słowo uzyskiwane przez dołączenie słowa y na końcu słowa x, czyli słowo x₁ … x_my₁ … y_n. W przypadku wielokrotnej konkatenacji słowa ze sobą samym używamy zapisu wykładniczego x^k, oznaczającego

k

xx … x.

Porządek leksykograficzny słów jest tożsamy z dobrze znanym porządkiem słownikowym. Będziemy od czasu do czasu używać zmodyfikowanego porządku leksykograficznego, nazywanego shortlex, który jest identyczny z porządkiem leksykograficznym, z wyjątkiem tego, że krótsze słowa poprzedzają dłuższe. Tym samym porządek shortlex wszystkich słów nad alfabetem {0,1} to

(ε, 0, 1, 00, 01, 10, 11, 000, …).

Mówimy, że słowo x jest prefiksem (przedrostkiem) słowa y, jeśli istnieje takie słowo z, że xz = y, przy czym x nazywamy prefiksem właściwym słowa y, jeśli dodatkowo x ≠ y.

Język jest zbiorem słów. Język nazywamy przedrostkowym, jeśli żaden element (słowo) języka nie jest prefiksem właściwym innego elementu.