Alfabet (informatikk)

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk

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 \Sigma, skriver man \Sigma^* for å uttrykke mengden av alle endelige strenger over alfabetet \Sigma. Her indikerer {}^* Kleene-stjerne-operatoren. Man skriver \Sigma^\infty (eller av og til \Sigma^\N eller \Sigma^\omega) for å uttrykke mengden av alle uendelige følger over alfabetet \Sigma.

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.