V informatike je abeceda konečná neprázdna množina. Prvky abecedy sa nazývajú písmená alebo symboly abecedy. Abecedu často značíme veľkým písmenom gréckeho písma, zvyčajne Σ (Sigma). Dôležitou vlastnosťou abecedy v teórii formálnych jazykov je jej konečnosť — umožňuje definovať všetky pojmy týkajúce sa reťazcov, jazykov a výpočtov striktne a formálne.
Príklady abecied
Príkladom abecedy je { - , ⋅ } {\displaystyle \{-,\cdot \}}
, ktorá sa môže používať pre Morseovu abecedu, alebo {begin, if, else, for, while}, čo môžu byť kľúčové slová programovacieho jazyka.
Okrem nich sa v praxi často používajú:
- binárna abeceda {0,1} — základ pri práci s binárnymi dátami a pri štúdiu teórie automatov;
- desiatková abeceda {0,1,2,3,4,5,6,7,8,9} — pre reprezentáciu čísel v textovej forme;
- ASCII alebo Unicode — štandardné množiny znakov používané v programovaní a spracovaní textu (tieto množiny sú síce veľké, ale ich podmnožiny používané ako abecedy sú často konečné);
- kľúčové slová a tokeny programovacích jazykov (napr. if, else, while), symboly protokolov a pod.
Množina prirodzených čísel nie je abeceda, pretože nie je konečná. V teoretickej literatúre sa však občas študujú nekonečné abecedy (napr. pri práci s neobmedzenými množinami symbolov), ale väčšina základných výsledkov teórie jazykov predpokladá konečnosť abecedy.
Reťazce (slová) nad abecedou
Abecedu, ktorá sa v informatike používa najčastejšie, je {0,1}. Nazýva sa binárna abeceda, pretože obsahuje dva symboly. Abecedu možno použiť na vytvorenie reťazca (alebo slova). Je to konečná postupnosť písmen z abecedy. Napríklad reťazec dĺžky 5 nad {0,1} je 01101. Dĺžku reťazca w značíme |w| (napr. |01101| = 5).
Prázdny reťazec je reťazec neobsahujúci žiadne písmená (často sa zapisuje ako λ {\displaystyle \lambda } 
). Prázdny reťazec je reťazec nad ľubovoľnou abecedou. Z hľadiska operácií platí, že pre ľubovoľný reťazec w je λ·w = w·λ = w (kde · je operácia zreťazenia).
Kleenova hviezda, mocniny a množiny reťazcov
Ak máme abecedu s názvom Σ {\displaystyle \Sigma } 
, potom množinu všetkých reťazcov, ktoré možno vytvoriť zo Σ {\displaystyle \Sigma }, zapíšeme ako Σ ∗ {\displaystyle \Sigma ^{*}} 
. Táto množina sa nazýva Kleenova hviezda (alebo Kleenov uzáver) Σ {\displaystyle \Sigma } . Je pomenovaná po matematikovi Stephenovi Coleovi Kleeneovi.
Kleenova hviezda binárnej abecedy je { λ , 0 , 1 , 00 , 01 , 10 , 11 , 000 , 001 , . . . } {\displaystyle \{\lambda ,0,1,00,01,10,11,000,001,...\}} 
. Tri bodky za číslom 001 ukazujú, že Kleenovu hviezdu abecedy nemôžeme zapísať celú, pretože je to nekonečná množina.
Formálne možno zapísať Σ* ako zjednotenie množín Σ^n pre všetky prirodzené n: Σ* = ⋃_{n≥0} Σ^n, pričom Σ^0 = {λ} a Σ^{n+1} = Σ^n · Σ (zreťazenie každého reťazca z Σ^n s každým symbolom zo Σ). Pozitívnu uzáver (bez prázdneho reťazca) značíme Σ+ = ⋃_{n≥1} Σ^n = Σ · Σ*.
Jazyky nad abecedou a ich význam
Jazyk nad abecedou Σ je ľubovoľná podmnožina Σ*. Jazyk teda určuje, ktoré reťazce zo Σ* sú „prijateľné“ alebo „patria do jazyka“. Formálne jazyky sú základom teórie formálnych jazykov, ktorá rozdeľuje jazyky podľa ich zložitosti: regulárne jazyky, bezkontextové jazyky, kontextovo-závislé jazyky a rekurzívne/rekurzívne preklinateľné jazyky.
Abecedy a jazyky sú kľúčové pri štúdiu formálnych jazykov, konečných automatov a veľmi zložitých otázok v informatike o tom, čo sa dá vypočítať a čo nie. Na úrovni aplikácií sa používajú pri lexikálnom analyzátore kompilátorov, pri popise protokolov, pri spracovaní textu, kódovaní dát a pri návrhu formálnych špecifikácií.
Bežné operácie nad reťazcami a jazykmi
- Zreťazenie reťazcov: ak sú u a v reťazce, potom u·v je ich zreťazenie (napr. "ab" = "a"·"b").
- Dĺžka: |w| je počet symbolov v reťazci w.
- Reverzný reťazec: w^R je reťazec w napísaný odzadu.
- Prefixy, sufixy, podreťazce: štandardné pojmy pri práci s textami.
- Operácie nad jazykmi: zjednotenie (L1 ∪ L2), prienik (L1 ∩ L2), doplnok, zreťazenie jazykov (L1·L2 = {uv | u∈L1, v∈L2}) a Kleenov uzáver L* = ⋃_{n≥0} L^n.
Praktické poznamky
- V implementácii a praxi sa často používa bitová abeceda {0,1} a bytové abecedy (množiny hodnôt 0–255) pre reprezentáciu dát.
- Pri práci s textom je potrebné rozlišovať medzi logickou abecedou (množina znakov, nad ktorými sa definuje jazyk) a fyzickým kódovaním (napr. UTF-8), ktoré určuje, ako sú znaky uložené v pamäti.
- V teórii výpočtov slúži abeceda len ako základný stavebný prvok; zložitosť problémov závisí hlavne od pravidiel jazyka a od modelu výpočtu (automat, gramatika, Turingov stroj).
Abecedy teda tvoria základný stavebný kameň formálnych jazykov a teórie automatov — umožňujú presné definície reťazcov, jazykov a operácií nad nimi, čo je nevyhnutné pre mnoho oblastí informatiky od lexikálneho analyzátora až po štúdium hraníc výpočtovateľnosti.