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:
| De man | slaat | de hond | |
| <naamwoordelijk deel> onderwerp |
<werkwoordelijk deel> werkwoord |
<naamwoordelijk deel> lijdend voorwerp |
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.
| <eenvoudige zin> ::= | <naamwoordelijkdeel><werkwoordelijk deel><naamwoordelijk deel> | |
| <naamwoordelijk deel> ::= | <lidwoord><zelfstandig naamwoord> | |
| <zelfstandig naamwoord> ::= | auto | man | hond | |
| <lidwoord> ::= | de | het | een | |
| <werkwoordelijk deel> ::= | slaat | eet | stuurt | voert |
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
| Wij | vliegen | gieren | naar | Artis | ||
| 1 . | <voornaamwoord> | <werkwoord> | <zelfstandignaamwoord> | <voorzetsel> | <zelfstandig naamwoord> | |
| 2. | <voornaamwoord> | <zelfstandig naamwoord> | <werkwoord> | <voorzetsel> | <zelfstandig naamwoord> |
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 a1a2...an.
De elementen ai 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 = a1a2...am
met ai Î 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 = a1a2...am
en y = b1b2...bn
dan is dus xy = a1a2...amb1b2...bn.
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 L1 en L2 formele talen zijn, dan is hun
verzamelingstechnische concatenatie de taal L1L2 = {xy | x
ÎL1, y Î L2}.
Voorbeeld
L1 = (01, 0}, L2 = {e , 0, 10}
Dan is L1L2 = {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 L2.
De algemene definitie luidt:
L0 = {e}
L1 = L
Li = LLi-1 = Li-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}.
S2 is de notatie voor alle strings in S+ met lengte twee, S3
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