Språkteori for NPC problemer

Et alfabet er en endelig mengde med ulike symboler. Et språk over alfabetet er enhver mengde bestående av strenger produsert med symboler i alfabetet.

$\sum$ - Alfabet $L$ - Språk $ϵ$ - Den tomme strengen

---

Språket som omfatter alle mulige strenger fra alfabetet, $\sum$, inkludert den tomme strengen kalles vi

\sum\,^* =\{0,1\}^* = \{\epsilon,0, 1,00,01,10,11,000,\dots\}

---

Eksempel

Det binære alfabetet, $\sum =\{0,1\}$, kan eksempelvis ha følgende språk:

• $L_0=\{0,1,11\}$
• $L_1=\{11111,1001\}$
• $L_2=\{10,11,101,111,\dots \}$ (som er alle primtall)