Formele talen

Een formele taal is een soort veralgemening van het begrip taal, zoals we dat uit het dagelijks leven kennen.

Basisbegrippen

We kunnen een formele taal om te beginnen zien als een gewone taal, bijvoorbeeld het Nederlands. Waaruit bestaat zo'n taal? Uit woorden, die we vervolgens samenvoegen tot zinnen. Zinnen laten we buiten beschouwing, we kijken alleen naar woorden. Waaruit bestaan woorden? Uit letters van het alfabet. Met het alfabet beginnen we dus.

Een alfabet is een willekeurige niet-lege verzameling. De elementen van een alfabet noemen we symbolen. Bij het Nederlands is dat het gewone Nederlandse alfabet met zowel kleine letters als hoofdletters, plus letters met trema en accenten. Willen we geen taal beschrijven maar bijvoorbeeld getallen, dan bevat het alfabet alle tien de cijfers. Een alfabet geven we vaak aan met het symbool Σ.

Met een woord, ook wel een string genoemd, bedoelen we een eindige rij symbolen uit een alfabet Σ. Neem bijvoorbeeld het alfabet Σ= {a,b,c,d,e,…, z}. Dan zijn “hallo” en “boterham” woorden, maar “café” niet (de letter “é” zit er niet in), “Daan” ook niet (de letter “D” zit er niet in) en “goede dag” evenmin (er is geen spatie). Met de lengte van een woord bedoelen we het aantal symbolen waaruit het woord bestaat.

Concatenatie van woorden: als we twee woorden a = a₁a₂… a_n en b = b₁b₂… b_m hebben, dan ontstaat door concatenatie het woord ab = a₁a₂… a_nb₁b₂… b_m. Voorbeeld: door de woorden “hallo” en “boterham” te concateneren ontstaat het woord “halloboterham”. Concatenatie geven we aan met een rondje, dus a ∘ b, of helemaal niet: dan schrijven we de woorden gewoon achter elkaar, zonder speciaal symbool voor concatenatie.

Het lege woord noteren we met ε. Dat is het woord met lengte nul. Als we een woord a = a₁… a_n concateneren met het lege woord ε, krijgen we weer het woord a. Er geldt dus a ∘ ε = a.

De afsluiting van een alfabet Σ is de verzameling van alle woorden die we uit het alfabet Σ kunnen maken, inclusief het lege woord. De afsluiting noteren we als Σ^∗. Bij het binaire alfabet Σ= {0, 1} geldt

$${\mathrm{\Sigma }}^{\ast }=\{\epsilon ,0,1,00,01,10,11,000,001,\dots \}$$

Soms gebruiken we ook de positieve afsluiting van een alfabet. Dat zijn weer alle woorden die we uit het alfabet kunnen samenstellen, behalve het lege woord. De positieve afsluiting noteren we als Σ⁺ en er geldt Σ⁺ = Σ^∗ ∖ {ε}.

Voorbeelden van alfabetten

• We gaan terug naar het voorbeeld met het Nederlands. Elk Nederlands woord zit in de afsluiting van een alfabet dat kleine letters, hoofdletters en varianten met diakritische tekens bevat (plus eventueel het koppelteken “-”). Als we aan dit alfabet ook de spatie en de leestekens (komma, punt, uitroepteken, vraagteken, …) toevoegen, dan bevat de afsluiting alle zinnen die we in het Nederlands kunnen vormen. Natuurlijk zitten in die afsluiting ook zinnen als “sadflsf kasdf kagrjewiaaeoker kf fkjbsjbgvbadfgsa!!!:??: ::!?:?:sdf”, die toch nog altijd zinvoller zijn dan de gemiddelde reactie onder een nieuwsbericht.

• Als ons alfabet alle cijfers bevat, Σ= {0, 1, …, 9}, dan zitten in de afsluiting alle natuurlijke getallen — en nog wat extra's. Er zitten namelijk ook getallen in die met een nul beginnen, zoals 00054, of alleen een nul, en bovendien het lege woord, dat natuurlijk geen getal is.

• Een alfabet mag niet leeg zijn, dus het kleinste alfabet heeft minstens één symbool. Bij het alfabet Σ= {!} krijgen we bijvoorbeeld de afsluiting Σ^∗ = {ε, !, !!, !!!, !!!!, …}, dus een verzameling woorden waarin voor elke n ∈ ℕ₀ precies één woord met n uitroeptekens zit en geen enkel ander woord.

• Laat Σ= {qw,c}. Dit is een heel vreemd alfabet, want het bevat het “woord” qw. Zo'n notatie wordt meestal niet gebruikt, omdat ze verwarrend en raar is, maar we kunnen het ons zo voorstellen dat we de letters “q” en “w” aan elkaar plakken tot één teken. Dan zien we “qw” als één symbool “qw”. Maken we van dit symbool het woord “qwcqw”, dan heeft dat woord lengte drie — het bestaat uit de symbolen “qw”, “c” en “qw”. Zulke alfabetten kom je niet vaak tegen, maar er zijn situaties waarin we symbolen nodig hebben die uit meerdere tekens bestaan.

Formele taal

Een (formele) taal over een alfabet Σ is een willekeurige deelverzameling van Σ^∗. Voor een taal L over een alfabet Σ geldt dus L ⊆ Σ^∗. Voorbeelden van talen:

• In het vorige deel hebben we het alfabet van cijfers Σ= {0, 1, …, 9} gedefinieerd. De afsluiting bestaat uit alle woorden die alleen uit cijfers zijn opgebouwd. Als we de regel toevoegen dat een woord niet met een nul mag beginnen en niet leeg mag zijn, krijgen we de verzameling van de natuurlijke getallen ℕ. Er geldt ℕ ⊆ Σ^∗, dus ℕ is een taal over het alfabet Σ.

• Aan de vorige verzameling cijfers kunnen we ook het minteken “-” toevoegen, dus Σ= {0, 1, …, 9, −}. De afsluiting bestaat dan uit alle woorden die uit cijfers of het minteken zijn opgebouwd. Dat betekent echter dat er in de afsluiting ook woorden zitten als “12-84-”, “1-5-8” of “-”. De taal van de gehele getallen ℤ maken we door drie regels toe te voegen:

  • Het minteken komt in het woord helemaal niet voor of staat vooraan in het woord.
  • Het eerste cijfer in het woord mag geen nul zijn, behalve in het woord “0”.
  • Elk woord moet minstens één cijfer bevatten.

  Deze verzameling beschrijft de verzameling van de gehele getallen en is een deelverzameling van Σ^∗ — het is dus een taal over het alfabet Σ.

• Laat Σ= {0, 1}. De afsluiting bestaat dan uit alle woorden die uit nullen en enen zijn opgebouwd. Een taal L over dit alfabet kunnen we bijvoorbeeld definiëren als de verzameling van alle woorden met precies drie enen. We kunnen ook creatiever zijn en zeggen dat de taal L de verzameling is van alle woorden die een geldig docx-bestand voorstellen (wat uit Word komt).

• We blijven bij het binaire alfabet Σ= {0, 1}. Elke string van tekens (gewone tekens van je toetsenbord) kunnen we omzetten naar binaire vorm, dus naar nullen en enen, en weer terug, bijvoorbeeld met de ASCII-tabel (of preciezer: de ASCII-tabel zet tekens om in getallen en getallen uit het tientallig stelsel kunnen we omzetten naar getallen in het tweetallig stelsel). Zo kunnen we de taal definiëren van alle woorden die overeenkomen met een geldig e-mailadres, en dat blijft een taal over het binaire alfabet.

Concatenatie van talen: we kunnen ook talen concateneren. De definitie lijkt op die van het cartesisch product van verzamelingen. Neem twee talen L₁ en L₂. Door ze te concateneren, L₁ ∘ L₂, krijgen we een nieuwe taal, die we als volgt definiëren:

$$L_1\circ L_2=\{w_1\circ w_2|w_1\in L_1,w_2\in L_2\}$$

We nemen dus alle woorden uit de taal L₁ en concateneren ze met alle woorden uit de taal L₂. Voorbeeld: laat

$$\begin{array}{rcl}{L}_1& =& \{0,1\}\\ L_2& =& \{a,b,hallo\}\end{array}$$

Dan geldt:

$$\begin{array}{rcl}{L}_1\circ L_2& =& \{0a,0b,0hallo,1a,1b,1hallo\}\\ L_2\circ L_1& =& \{a0,a1,b0,b1,hallo0,hallo1\}\\ L_1\circ L_1& =& \{00,01,10,11\}\end{array}$$

Tot nu toe hebben we talen beschreven met gewone taal: we hebben gewoon in woorden beschreven hoe de taal eruit moet zien. Dat is echter erg onpraktisch, dus er wordt een formelere manier ingevoerd om een taal te definiëren. De eerste daarvan is de grammatica.