∑ 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,...}