Inden for datalogi er et alfabet et endeligt ikke-tomt sæt. Elementerne i et alfabet kaldes bogstaver eller symboler i alfabetet.

Et eksempel på et alfabet er { - , ⋅ } {\displaystyle \{-,\cdot \}}{\displaystyle \{-,\cdot \}}, som kan bruges til morsekode, eller {begin, if, else, for, while}, som kan være nøgleord i et programmeringssprog.

Mængden af naturlige tal er ikke et alfabet, fordi den ikke er endelig.

Det alfabet, der bruges mest inden for datalogi, er {0,1}. Det kaldes det binære alfabet, fordi det indeholder to symboler. Et alfabet kan bruges til at lave en streng (eller et ord). Dette er en endelig sekvens af bogstaver fra alfabetet. F.eks. er en streng af længde 5 over {0,1} 01101.

Den tomme streng er den streng, der ikke indeholder nogen bogstaver (den skrives ofte som λ {\displaystyle \lambda }{\displaystyle \lambda } ). Den tomme streng er en streng over et hvilket som helst alfabet.

Hvis vi har et alfabet kaldet Σ {\displaystyle \Sigma } {\displaystyle \Sigma }. Så skriver vi mængden af alle strenge, der kan laves ud fra Σ {\displaystyle \Sigma }{\displaystyle \Sigma } som Σ ∗ {\displaystyle \Sigma ^{*}} {\displaystyle \Sigma ^{*}}. Dette kaldes Kleene-stjernen (eller Kleene-lukningen) af Σ {\displaystyle \Sigma } {\displaystyle \Sigma }. Den er opkaldt efter matematikeren Stephen Cole Kleene.

Kleene-stjernen i det binære alfabet er { λ , 0 , 0 , 1 , 00 , 01 , 10 , 11 , 000 , 001 , . . . } {\displaystyle \{\lambda ,0,1,00,00,01,10,11,000,001,...\}} {\displaystyle \{\lambda ,0,1,00,01,10,11,000,001,...\}}. De tre prikker efter 001 viser, at vi ikke kan skrive Kleene-stjernen for et alfabet i sin helhed, fordi det er en uendelig mængde.

Alfabeter er vigtige, fordi de bruges til at studere formelle sprog, finite automater og meget vanskelige spørgsmål inden for datalogi om, hvad der kan beregnes, og hvad der ikke kan beregnes.

Formel definition af Kleene-stjernen

Formelt defineres Kleene-stjernen for et alfabet Σ {\displaystyle \Sigma }{\displaystyle \Sigma } som

Σ* = ⋃n ≥ 0 Σn, hvor

  • Σ0 = {λ} (kun den tomme streng),
  • Σ1 = Σ,
  • for n ≥ 1 er Σn mængden af alle strenge, der er concatenation (sammensætning) af n symboler fra Σ.

En nært beslægtet notation er Σ+ = ⋃n ≥ 1 Σn, som er alle ikke-tomme strenge over Σ. Hvis alfabetet Σ er ikke-tomt, er både Σ* og Σ+ uendelige mængder (countable uendelige).

Grundlæggende begreber om strenge

  • Konkatenation: Hvis x og y er strenge over Σ, så er xy deres konkatenation (først x så y). Konkatenationen er associativ.
  • Længde: |w| angiver antallet af symboler i strengen w. Den tomme streng λ har længde 0.
  • Substring og præfiks: Et ord u er en præfiks af w, hvis der findes v så w = uv. Ligeledes er u en suffix af w, hvis w = vu.
  • Omvendt streng: For en streng w = a1a2...an er wR = an...a2a1.

Sprog og operationer på sprog

Et sprog er en mængde af strenge over et alfabet Σ, dvs. et vilkårligt sæt L ⊆ Σ*. Sprog studeres ofte med følgende operationer:

  • Union: L1 ∪ L2,
  • Konkatenation: L1L2 = {xy | x ∈ L1, y ∈ L2},
  • Kleene-stjerne på sprog: L* = ⋃n ≥ 0 Ln, hvor L0 = {λ}.

Disse operationer er centrale i teorien om regulære sprog og regulære udtryk.

Eksempler og afklaring

For det binære alfabet Σ = {0,1} er Σ* = {λ, 0, 1, 00, 01, 10, 11, 000, 001, 010, ...}. Bemærk, at Σ* indeholder alle endelige binære strenge, og derfor er det en uendelig mængde. Den tomme streng skrives ofte som λ eller ε afhængigt af litteraturen.

Anvendelser og betydning i datalogi

Alfabeter og strenge er fundamentale byggesten i mange områder af datalogi:

  • Formelle sprog og automater (finite automater, pushdown-automater, Turingmaskiner) modellerer hvilke sprog der kan genkendes af forskellige beregningsmodeller.
  • Regulære udtryk og parserteknikker i programmeringssprog bruger opsætningen af alfabet, strenge og sprog til at beskrive syntaks og mønstre.
  • Informationsteori og kodning (fx binære koder, morsekode) bygger på at repræsentere information som strenge over et alfabet.
  • Teoretiske resultater om beregnelighed og kompleksitet klassificerer problemer efter, hvilke sprog de svarer til, og hvilke maskiner der kan beslutte dem.

Bemærkninger og terminologi

  • Nogle definitioner tillader et tomt alfabet (Σ = ∅), men i denne artikel antager vi det almindelige krav om, at alfabetet er endeligt og ikke-tomt.
  • Symbolerne for den tomme streng kan variere: både λ og ε er almindelige.
  • Selvom Σ er endeligt, er Σ* altid en (tælleligt) uendelig mængde, fordi der findes strenge af vilkårlig længde.

Videre læsning

For at gå videre kan man studere:

  • Regulære sprog og regulære udtryk (og deres ekvivalens med finite automater).
  • Kontekstfrie sprog og pushdown-automater.
  • Turingmaskiner og besluttelighed/uberettelighed i forbindelse med sprog.