W informatyce alfabet to skończony, niepusty zestaw symboli. Elementy alfabetu są nazywane literami lub symbolami alfabetu.

Przykłady i uwagi

Przykładem alfabetu może być zbiór zawierający dwa symbole: {-, ⋅} {\displaystyle \{-,\cdot \}}. Taki prosty alfabet może być użyty np. w kodzie Morse'a lub do reprezentowania operatorów i znaków w języku programowania.

Z drugiej strony, zbiór liczb naturalnych nie jest alfabetem, ponieważ nie jest skończony (alfabet musi mieć skończoną liczbę symboli).

Ciągi (słowa) nad alfabetem

Alfabet może być używany do tworzenia ciągów (zwanych też słowami). Ciąg nad alfabetem to skończona sekwencja liter z tego alfabetu. Długość ciągu w liczbie liter oznaczamy zwykle jako |w|. Przykładowo, nad alfabetem binarnym {0,1} (nazywanym alfabetem binarnym) ciągiem długości 5 jest słowo 01101.

Pusty ciąg

Pusty ciąg to ciąg nie zawierający żadnych liter; oznaczany jest zwykle jako λ {\displaystyle \lambda } (albo czasem jako ε). Pusty łańcuch należy do Σ* dla dowolnego alfabetu Σ i ma długość |λ| = 0.

Notacja Σ i zamknięcie Kleene'a (gwiazda Kleene'a)

Jeżeli mamy alfabet o nazwie Σ {\i1}Sigma {\i0} {\displaystyle \Sigma }, to oznaczamy przez Σ* zbiór wszystkich możliwych (skończonych) ciągów nad Σ {\displaystyle \Sigma }{\displaystyle \Sigma ^{*}}. Ten zbiór nazywa się Gwiazdą Kleenowa (lub zamknięciem Kleenowym) alfabetu Σ {\displaystyle \Sigma }; nazwa pochodzi od matematyka Stephena Cole Kleene'a.

Formalnie można zapisać:

  • Σ^0 = {λ},
  • Σ^n = zbiór wszystkich ciągów długości n nad Σ (dla n > 0),
  • Σ* = ⋃_{n≥0} Σ^n = Σ^0 ∪ Σ^1 ∪ Σ^2 ∪ ...
Można też zdefiniować Σ+ = ⋃_{n≥1} Σ^n = Σ* \ {λ}, czyli zbiór wszystkich niepustych ciągów nad Σ.

Przykładowo, Gwiazda Kleenowa alfabetu binarnego to {\displaystyle \{\lambda ,0,1,00,01,10,11,000,001,...\}} czyli {λ, 0, 1, 00, 01, 10, 11, 000, 001, ...}. Trzy kropki po 001 oznaczają, że zbiór jest nieskończony i nie możemy go wypisać w całości.

Zastosowania i znaczenie

Alfabety są podstawowym pojęciem w teorii języków formalnych, w analizie automatów skończonych, w konstrukcji wyrażeń regularnych oraz w wielu dziedzinach informatyki związanych z przetwarzaniem symboli. Poznanie, jakie słowa można utworzyć nad danym alfabetem (i jakie struktury tych słów spełniają określone reguły), pomaga odpowiadać na kluczowe pytania w informatyce, takie jak: co można policzyć, jakie maszyny potrafią rozpoznawać dane języki oraz jakie problemy są nierozwiązywalne.

Podsumowując: alfabet to skończony, niepusty zbiór symboli; na jego podstawie definiujemy słowa (skończone ciągi), pusty ciąg λ oraz zbiór wszystkich słów Σ* zwany gwiazdą Kleene'a, który odgrywa centralną rolę w teorii języków i automatyce.