Formele talen

Inleiding  |  Wiskunde  |  Formele taal

Inleiding
Bij het bestuderen van een taal (of dat nu een levende of een formele is) hebben we allemaal wel een bepaald voordeel.
Iedereen is in ieder geval expert in minstens ??n taal: zijn of haar moedertaal. Of dit nu Engels, Frans, Spaans of Nederlands is, we zijn er zeer vaardig in en we ontwikkelen deze vaardigheid gedurende ons hele leven verder.
Behalve ??n of meer natuurlijke (levende) talen beheersen velen van ons tegenwoordig ook programmeertalen, zoals Basic, COMAL, Pascal of C++. In deze talen worden programma's voor computers geschreven en zij (die talen) moeten dus op de een of andere manier met computers kunnen communiceren. Die communicatie verloopt in een aantal gevallen echter niet goed, mogelijk doordat de computer niet erg bedreven is in het begrijpen van de gebruikte taal, of doordat de schrijver van het programma fouten heeft gemaakt waardoor de computer op het verkeerde been wordt gezet.
In natuurlijke talen kunnen we heel goed met elkaar communiceren in slecht gestructureerde of onvolledige zinnen, maar computers hebben (helaas) aan een half woord niet genoeg. Computerprogramma's moeten zich houden aan zeer strenge (en strikte) regels: de kleinste afwijking van die regels wordt als incorrect door de computer afgewezen.

In het ideale geval is een zin in een taal zowel semantisch (naar betekenis) als syntactisch (naar grammaticale structuur) correct. Wanneer wij zelf in het Nederlands met elkaar communiceren zijn zinnen vaak syntactisch onjuist, terwijl toch de bedoelde semantiek feilloos wordt overgedragen. In programmertalen is syntactische correctheid essentieel: een noodzakelijke voorwaarde om de betekenis van het programma te kunnen overdragen.

Als we de semantiek van een zin bestuderen, dan bestuderen we de betekenis van die zin. De volgende zinnen hebben alle dezelfde semantische interpretatie, en dus dezelfde betekenis:

De man slaat de hond.
De hond wordt door de man geslagen.
L'homme frappes le chien.

Het bestuderen van de syntaxis of de grammmatica is het bestuderen van de zinsstructuur (de ontleding). De zin

De man slaat de hond.

kan worden ontleed in zijn samenstellende grammaticale delen:

Elk zin met deze structuur is syntactisch correct Nederlands. Een verzameling van dit soort eenvoudige zinnetjes kunnen we met behulp van de volgende regels beschrijven.

De regels zijn geformuleerd met behulp van de Backus-Naur Form (BNF). Dit is een notatie die vaak wordt gebruikt bij het beschijven van de syntaxis van programmeertalen.
In het voorbeeld wordt het begrip <eenvoudige zin> gedefinieerd (via het teken ::=, dat uitgesproken wordt als "wordt gedefinieerd als") met behulp van twee andere begrippen <naamwoordelijk deel> en <werkwoordelijk deel>; in gewoon Nederlands:
een eenvoudige zin wordt gedefinieerd als een naamwoordelijk deel gevolgd door een werkwoordelijk deel en (opnieuw) gevolgd door een naamwoordelijk deel.
Een <naamwoordelijk deel> bestaat uit een <lidwoord> gevolgd door een <zelfstandig naamwoord>.
Voor een <lidwoord> kunnen we kiezen uit een drietal woorden (taalcomponenten): de ?f het ?f een (het teken | wordt uitgesproken als "?f"). Voor een zelfstandig naamwoorden kunnen we in dit geval kiezen uit auto, man en hond, terwijl de keuze van het <werkwoordelijk deel> beperkt is tot een woord uit de rij stlaat, eet, stuurt en voert.
We kunnen nu door een keuze syntactisch juiste, maar soms semantisch onjuiste, <eenvoudige zin>nen maken als:

de man slaat de hond
een hond eet de auto
het auto stuurt het man
het hond voert het hond

In totaal kunnen we met bovenstaande regels (3 x 3) x 4 x (3 x 3) = 384 verschillende zinnen maken. Ze zijn all syntactisch correct, maar hun betekenis kan raadselachtig zijn (wat betekent bijvoorbeeld de zin "de auto voert de man"?).

We bekijken veder de volgende, syntactisch correcte, Nederlandse zin:

Wij vliegen gieren naar Artis.

Hieronder staan twee mogelijke ontledingen

De betekenis van 1. is een mededeling van enkele piloten, dat zij roofvogels naar een dierentuin in Amsterdam brengen. De betekenis van 2. is een mededeling afkomstig van een groep insecten die met grote snelheid op weg zijn naar dezelfde dierentuin.
Verschillende ontledingen leiden dus to verschillende semantische interpretaties. Hoewel dit een ietwat gekunsteld voorbeeld is (in ons dagelijks taalgebruik komt dit soort misverstanden niet vaak voor), is dit fenomeen voor het werken met computerprogramma's wel degelijk van belang. Een cruciale stap tijdens compileren (geschikt maken voor interpretatie door computers) van programma's is het ontleden ervan om het samentisch te kunnen interpreteren (het ontleedproces wordt dikwijls met de Engelse term "parsing" aangeduid).

Wiskunde
Bij de bestudering van formele talen wordt vaak gebruik gemaakt van wiskundige begrippen als verzameling, kardinaliteit, grafen en recursiviteit.
We zullen een en ander toelichting via het begrip "string" dat in de formele taalkunde tot de basisbegrippen behoort.

Met een string bedoelen we een eindige rij symbolen a₁a₂...a_n. De elementen a_i zijn afkomstig uit een eindige verzameling S, die we alfabet noemen. In een string zijn herhalingen van hetzelfde symbool (teken, letter) toegestaan. Zo is 001110110 een voorbeeld van een string met symbolen uit het alfabet S = {0, 1}.
Van een string bestaande uit k symbolen zeggen we dat hij de lengte k heeft. 001110110 heeft dus de lengte 9. Een string zonder symbolen (de lege string) heeft de lengte 0. We duiden de lege string aan met e. De lengte van een string x wordt vaak genoteerd als |x|. Dus |001110110|=9 en |e|=0.

De verzameling van alle mogelijke strings over een alfabet S zullen we noteren als S*. Dus, uitgaande van S = {0, 1} hebben we

S* = {e, 0, 1, 00, 01, 10, 11, 000, 001, 010, ... }

Als x ? S* een string is met lengte m, dan schrijven we x = a₁a₂...a_m met a_i ? S voor 1 ? i ? m.
Als x ? S* een string is met lengte m en Als y ? S* een string is met lengte n, dan heet de string die wordt gevormd door de string y rechts aan de string x toe te voegen de concatenatie van x en y, notatie xy. In dit geval is dus |xy| = m + n.
Is x = a₁a₂...a_m en y = b₁b₂...b_n dan is dus xy = a₁a₂...a_mb₁b₂...b_n. De operatie concatenatie is associatief: (xy)z = x(yz), maar niet commutatief, omdat meestal xy ? yx.
De lege string is het eenheidselement ten opzichte van concatenatie, omdat ex = xe = x voor alle x ? S*.

Formele taal
Met de in de vorige paragraaf vastgelegde begrippen kunnen we nu een formele taal defini?ren.
Een (formele) taal L over een alfabet S wordt gedefinieerd is een deelverzameling van S*.
Als twee L₁ en L₂ formele talen zijn, dan is hun verzamelingstechnische concatenatie de taal L₁L₂ = {xy | x ?L₁, y ? L₂}.
Voorbeeld
L₁ = (01, 0}, L₂ = {e , 0, 10}
Dan is L₁L₂ = {01, 010, 0110, 0, 00, 010}.
Uit dit voorbeeld moge blijken, dat de stringconcatenatie associatief, maar niet commutatief is.
Voor ieder taal geldt L{e} = L{e} = L. De verzameling {e} bestaande uit ?en element is dus een eenheidselement voor de concatenatie.
Merk hierbij op, dat deze taal niet hetzelfde is als de lege verzameling, die wordt aangeduid met ?. Immers L?=?L=? voor ieder taal L.

De concatenatie van een taal L met zichzelf is LL en wordt geschreven als L².
De algemene definitie luidt:
L⁰ = {e}
L¹ = L
Lⁱ = LL^i-1 = L^i-1L voor i = 2, 3, ...

De Kleene-afsluiting van een taal L, notatie L*, is gedefinieerd als

L+ is per definitie gelijk aan

Uit deze beide definities volgt: L* = L⁺ ? {e}.
S² is de notatie voor alle strings in S⁺ met lengte twee, S³ voor die met lengte 3, enz.
De verzameling van alle strings met lengte groter gelijk aan ?en wordt geschreven als S⁺.

Hieruit volgt dus:

[ftalen.htm] laatste wijziging op: 18-02-2007