Alfabet (informatikk)

Fra Wikipedia, den frie encyklopedi
Hopp 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 , 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.