Samenvatting talen

∑ is een alfabet, hierin staan alle mogelijke symbolen bijv.
  ∑ = {a,b,c}

λ is null oftewel leeg, het bevat niets.

L is een taal met woorden bijvoorbeeld met het alfabet hierboven:
L is een verzameling van woorden {}
  L={a,b,c,aa,ab,ac,bb,ba,bc,cc,ca,cb,aaa,aab,...}
De taal L met een lege string:
  L={λ,a,b,c,aa,ab,ac,bb,ba,bc,cc,ca,cb,aaa,aab,...}

De kleene ster geeft een verzameling woorden aan inclusief een lege string λ
  ∑*
is dus hetzelfde als:
  L={λ,a,b,c,aa,ab,ac,bb,ba,bc,cc,ca,cb,aaa,aab,...}
Sigma + geeft dezelfde verzameling maar dan zonder de lege string λ
  ∑+
oftwel:
  L={a,b,c,aa,ab,ac,bb,ba,bc,cc,ca,cb,aaa,aab,...}
Je kunt dan ook zeggen dat:
  ∑+=∑* - {λ}
  of
  ∑*=∑+ + {λ}

De maximale lengte van een woord kunnen we aangeven met |w| waarbij w de variable is waat het woord in komt.
Bijvoorbeeld:
  |w|≤2 
Geeft een maximale woordlengte van 2, met een ∑={a,b} geeft dat de taal:
L = {λ,a,b,aa,bb,ab,ba}
λ doet mee omdat de lengte 0 ook kleiner is dan 2

De inverse van een taal L' bevat alle woorden die niet in de taal L voorkomen.
Stel dat we een ∑={a,b} met de gegeven taal L={aa,bb} dan is de de inverse van de taal L':
L'={λ,a,b,ab,ba}

Als we de twee verzamelingen bij elkaar optellen L ∪ L' dan krijgen we weer alle mogelijke woorden ∑*

Het vorige voorbeeld kunnen we ook formeel opschrijven:
  L={w∈{a,b}* : |w| ≤ 2}
Hier staat:
  De taal L is een verzameling van woorden waarbij ieder woord w bestaat uit alle combinaties van het alfabet {a,b} waarbij de lengte van het woord w maximaal 2 is.

Bij een taal hoort ook een gramatica, je mag niet zomaar alle combinaties van letters maken in een taal.
Een gramatica is als volgt opgebouwd:
 G={V,T,S,P}
Waarbij:
 V zijn hulpsymbolen oftwel variablen altijd geschreven in een hoofdletter
 T zijn de eindsymbolen altijd geschreven in een kleine letters
 S is het startsymbool de eerste variable altijd geschreven in een hoofdletter
 P zijn de regels die bij de gramatica horen

Voorbeelden:
  S → y 
  De uitkomst is {y}
  
  S → a  
  De uitkomst is {a}
  
  S → aB
  B → b
  De uitkomst is {ab}
  
  S → aSb
  S → λ
  De uitkomst is {λ,ab,aabb,aaabbb,...}
  Of anders geschreven:
  L(G)={anbn : n ≥ 0}
  
  
  S → AB
  A → aAb | λ
  B → Bb | b
  De uitkomst is {b,abbb,abbbbbbbb,aabbbbb,...}