Alfabet (informatikk)

Et alfabet er i informatikk og predikatslogikk en endelig mengde symboler eller bokstaver. Det vanligste alfabetet er {0,1}, det binære alfabetet. En endelig streng er en endelig følge av bokstaver fra et alfabet; for eksempel er en binær streng en streng med bokstaver fra det binære alfabetet. Også en uendelig følge av bokstaver kan konstrueres med bokstaver fra et alfabet.

Gitt et alfabet , skriver man  for å uttrykke mengden av alle endelige strenger over alfabetet . Her indikerer  Kleene-stjerne-operatoren. Man skriver  (eller av og til  eller ) for å uttrykke mengden av alle uendelige følger over alfabetet .

For eksempel, hvis man bruker det binære alfabetet {0,1}, vil alle strengene (ε, 0, 1, 00, 01, 10, 11, 000, osv.) være i alfabetets Kleene-omfang.

Alfabeter er viktige i bruken av formelle språk, automater og semiautomater. Når man definerer spesifikke automater, er det i de fleste tilfeller nødvendig å spesifisere et alfabet som inputtstrengene til automaten er bygd opp fra.

Formelle språk