Abeceda v informatike: definícia, príklady a význam vo formálnych jazykoch

Abeceda v informatike: definícia, príklady (binárna abeceda, kľúčové slová), Kleenova hviezda a význam vo formálnych jazykoch, konečných automatoch a výpočtovej teórii.

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.

Otázky a odpovede

Otázka: Čo je to abeceda?

Otázka: Dá sa množina prirodzených čísel považovať za abecedu?

Otázka: Aká je najčastejšie používaná abeceda v informatike?

Otázka: Čo znamená vytvoriť reťazec z abecedy?

Otázka: Čo znamená Kleenova hviezda?

Otázka: Ako môžeme znázorniť Kleeneho hviezdu pre binárny alfbet?

Otázka: Prečo sú abecedy dôležité v informatike?

Hľadajte podľa písmena