Formele taal

De term formele taal heeft ten minste drie verwante betekenissen:

1. vormelijk taalgebruik;
2. taal waarvan de vorm en meestal betekenis exact vastliggen, meestal door middel van wiskundige definities;
3. een verzameling tekenreeksen.

Formeel taalgebruik

In het normale spraakgebruik is formele taal taalgebruik dat vormelijk is: het houdt zich aan conventies om datgene wat gezegd wordt te formuleren, die zelf weer een onderdeel zijn van conventies voor de manier waarop de communicatie plaatsvindt. Het tegenovergestelde is informeel taalgebruik, dat zich juist niet aan zulke conventies houdt.

Met formeel taalgebruik wordt, als alle partijen het beheersen, een specifieke context van communicatie gecreëerd waarin de communicatie veel preciezer kan zijn dan met informeel taalgebruik mogelijk is. Dit is in sterke mate het geval bij ambtelijk of juridisch taalgebruik, waarin heel veel gebruik wordt gemaakt van standaardformuleringen waarvan de betekenis zeer precies vast is komen te liggen, deels expliciet in wetsteksten en juridische uitspraken, deels impliciet door de lange geschiedenis van het gebruik van de formuleringen in eerdere communicatie over het desbetreffende onderwerp.

Kunstmatige taal

In de wetenschap, en met name in de wiskunde en informatica, is een formele taal een gecreëerde, kunstmatige taal waarvan vorm (de syntaxis) en vaak ook betekenis (de semantiek) exact is vastgelegd, vaak door middel van wiskundige definities. Formele talen worden bestudeerd en gebruikt in de wiskunde en de informatica en enige aanverwante disciplines. Het doel is ook hier om zeer precieze communicatie mogelijk te maken door de betekenis van uitdrukkingen en constructies zo exact mogelijk vast te leggen. Veel formele talen zijn expliciet ontworpen om door machines begrepen te worden; hieronder vallen de computertalen, die worden gebruikt om informatie op een computer op te slaan of het gedrag van een computer te programmeren. Daarnaast bestaan er informatierepresentatietalen of gegevensmodelleertalen. Voorbeelden van informatierepresentatietalen die zijn gebaseerd op een formalisering van natuurlijke talen zijn Gellish Formeel Nederlands en Gellish Formal English. Het tegenovergestelde van een kunstmatige taal is een natuurlijke taal: een taal zoals het Nederlands die door mensen wordt gebruikt om onderling te communiceren en in de loop van die communicatie geleidelijk is ontstaan. De taalkunde houdt zich bezig met de bestudering van natuurlijke talen.

Als vorm en betekenis van een taal volledig wiskundig vastliggen spreken we van een wiskundig formalisme. Zulke formalismen zijn de grondslag voor het bedrijven van wiskunde; bepaalde gebieden van de wiskunde en toepassingen ervan, zoals de mathematische logica en de theoretische informatica, houden zich uitvoerig bezig met het ontwerpen en bestuderen van dergelijke formalismen.

De wiskunde zelf is ontstaan doordat de vorm en inhoud van logische redeneringen hoe langer hoe meer geformaliseerd is, totdat de formaliseringen vastlagen die ook nu nog het meest worden gebruikt. Hierdoor ontstond een discussie over de grondslagen van de wiskunde waarin de grenzen van de wiskundige formaliseerbaarheid werden onderzocht; sommige wiskundigen meenden zelfs dat het wiskundige redeneren in wezen niet meer is dan formele, mechanisch uitvoerbare symboolmanipulatie (een standpunt dat het formalisme wordt genoemd). Hiermee werden ook de grondslagen gelegd voor de programmeerbare computer.

Tegelijkertijd ontstond in de taalkunde de behoefte om de vorm en betekenis van door mensen gesproken talen zoals het Nederlands precies te beschrijven. Een van de manieren om dit te doen is om een formele taal te definiëren die in vorm en betekenis de natuurlijke taal probeert te benaderen.

Deze benadering heeft een grote stimulans gekregen door het beschikbaar komen van computers voor algemeen gebruik, vanaf 1950, enerzijds omdat men wilde proberen computers begrip van natuurlijke taal bij te brengen – bijvoorbeeld voor automatisch vertalen – en anderzijds omdat men in begon te zien dat computerprogrammatuur moet worden geschreven in een taal die voor de menselijke programmeur zo begrijpelijk mogelijk moet zijn. Hierdoor ontstond onderzoek naar de vraag welke eigenschappen zulke talen moeten hebben en de vraag hoe zulke talen goed beschreven kunnen worden. Dit leidde tot het wiskundige vakgebied van de formeletalentheorie.

Baanbrekend werk op dit terrein is verricht door Noam Chomsky.

Taal in de formeletalentheorie

De formeletalentheorie, een zelfstandig onderzoeksgebied binnen de theoretische informatica, formele logica en mathematische taalkunde, is gewijd aan de bestudering van wiskundige formalismen om de vorm (syntaxis) van uitdrukkingen in formele talen mee te beschrijven. De inhoud (betekenis, semantiek) van uitdrukkingen wordt meestal volkomen buiten beschouwing gelaten.

Een taal is in de formeletalentheorie gedefinieerd als een verzameling tekenreeksen bestaande uit tekens gekozen uit een gegeven eindig alfabet. Zo'n verzameling fungeert als een predicaat: de definitie van een taal onderscheidt de grammaticale uitdrukkingen (de tekenreeksen die tot de taal behoren) van de ongrammaticale (de tekenreeksen die niet tot de taal behoren). Het begrip formele taal in deze zin is complementair aan het begrip van een formalisme in de wiskunde. In de wiskunde wordt de precieze definitie van de vorm van uitdrukkingen als tekenreeksen van symbolen tamelijk informeel afgedaan; het gaat om de betekenis van de uitdrukkingen. In de formeletalentheorie is deze precieze definitie juist het object van onderzoek.

Een voorbeeld is de verzameling natuurlijke getallen. De meeste wiskundigen beschouwen deze als gegeven, of onderzoeken hoe hun betekenis het best gedefinieerd kan worden; maar hun precieze notatie als $\mathbb {N} =\{0,1,2,\ldots \}$ beschouwen ze niet als onderwerp van onderzoek. In de formeletalentheorie gaat het juist om die precisering van notatie: het decimale, octale en binaire talstelsel zijn bijvoorbeeld drie verschillende talen.

Chomsky definieerde een natuurlijke taal als een formele taal in deze zin: de grammaticale zinnen in de taal kun je zien als een formele taal over het alfabet van de letters waar de taal mee wordt geschreven. De opdracht is dan om een precieze definitie van deze taal te vinden. Voor de meeste talen zijn er uitgebreide grammatica's die dit grotendeels beschrijven. Chomsky onderschatte echter de moeilijkheden bij het volledig doorvoeren van dit idee: zowel wat precies de elementaire eenheden zijn waar zinnen uit zijn opgebouwd als wat precies grammaticale zinnen zijn ligt voor natuurlijke talen niet precies vast. De zin van zijn uitgangspunt wordt dan ook door veel taalkundigen betwijfeld. Bovendien hoopte Chomsky een eenvoudig formalisme te vinden dat geschikt is om precies het soort taal te beschrijven waar bestaande natuurlijke talen voorbeelden van zijn; hij dacht daarbij in eerste instantie aan de contextvrije grammatica. Ook hierbij was hij te optimistisch: met dit formalisme kunnen inderdaad grammatica's worden gedefinieerd die de structuur van natuurlijke taal grofweg benaderen, maar voor exacte beschrijvingen van werkelijke talen zijn allerlei aanvullende mechanismen nodig.

Dit geldt ook in de informatica, maar toch worden de technieken van Chomsky, en uitbreidingen daarvan, daar routinematig toegepast bij de definitie van computertalen. Een toepassing is de exacte definitie van notaties, bijvoorbeeld de decimale notatie van natuurlijke getallen; zulke definities zijn meestal onderdeel van de definitie van ingewikkeldere talen, bijvoorbeeld een programmeertaal. Een tweede toepassing is om de algemene syntactische structuur van uitdrukkingen in ingewikkeldere talen te beschrijven: zo'n formele grammatica (vaak in BNF) beschrijft dan alle geldige uitdrukkingen, maar meestal zijn om alle ongeldige uitdrukkingen uit te sluiten aanvullende regels nodig, die meestal informeel of zelfs helemaal niet gesteld worden.

Definitie

Een formele taal $\mathbf {\mathit {L}}$ is een verzameling van woorden. Een woord uit een formele taal is een rijtje letters uit het (normaal gesproken eindige) alphabet $\mathbf {\mathit {\Sigma }}$. Het achter elkaar schrijven van letters of woorden heet concatenatie. Als men deze wil benadrukken wordt meestal $\circ$ of $\cdot$ gebruikt. Concatenatie is associatief, maar niet commutatief:

$\forall u,v,w:(u\circ v)\circ w=u\circ (v\circ w)=u\circ v\circ w$

maar

$\neg \forall u,v:u\circ v=v\circ u$

De concatentatieoperatie levert daarom de algebraïsche structuur van een monoïde over het gegeven alfabet.

Men geeft het lege woord, een rijtje zonder enige letter, meestal aan met $\varepsilon$. Verder wordt met verticale strepen meestal de lengtefunctie beschreven: Als $w$ een woord is, dan wordt met $|w|$ de lengte daarvan bedoeld, dus het aantal letters in het rijtje. We hebben $|\varepsilon |=0$, $\forall a\in \Sigma :|a|=1$ en $\forall v,w\in \Sigma ^{*}:|v\circ w|=|v|+|w|$ (waarbij $\Sigma ^{*}$ de taal van alle eindige rijtjes letters uit het alfabet $\Sigma$ is).

Voorbeeld: Neem $\Sigma =\{a,b,c\}$. Dan is a een woord in $\Sigma ^{*}$. Ook b is een woord in $\Sigma ^{*}$ en ook ab en aabbc en ook ababacacbacabbc. De lengte van het woord bac is drie en die van abaca is vijf.

Uiteraard kan een alfabet behalve tekens in het Romeinse alfabet zoals wij ze kennen allerlei andere tekens bevatten. Bijvoorbeeld $\Sigma =\{\alpha ,\beta ,\gamma \}$. Voor veel toepassingen weten we alleen dat we x verschillende symbolen hebben en is het niet zinvol aan ieder symbool een grafische weergave toe te kennen. In zo'n geval worden symbolen vaak genummerd, bijvoorbeeld: $\Sigma =\{0,1,2,3,4,5,6,7,8,9,10,11,12\}$. Een woord is dan een reeks getallen.

Een woord dat niet oneindig veel symbolen bevat, heeft een eindige lengte. De verzameling van alle mogelijke woorden in een alfabet $\Sigma$ met een eindige lengte wordt aangeduid met $\Sigma ^{*}$. Zo'n verzameling is dus oneindig groot, maar wel aftelbaar.

Een formele taal L is een deelverzameling van $\Sigma ^{*}$, dus:

$L_{\Sigma }\subseteq \Sigma ^{*}$

Klassen van talen

Een veelgebruikte hiërarchie om formele talen in te delen is de Chomskyhiërarchie, die talen indeelt van klasse 0 (alle talen) tot klasse 3. Elke klasse in de hiërarchie omvat ook de talen in de daaropvolgende klassen.

Klasse	Naam	Automatenmodel	Grammatica
	Alle talen	Geen (niet alle zijn beslisbaar)	Geen
Chomsky-0	Semibeslisbaar	Turingmachine	elke grammatica
Chomsky-1	Contextgevoelig	Lineair begrensde turingmachine	Contextgevoelige grammatica
Chomsky-2	Contextvrij	Stapelautomaat	Contextvrije grammatica
Chomsky-3	Regulier	Eindige automaat	Reguliere grammatica

Binnen de klasse contextvrije talen bestaan verschillende subklassen, die vooral van belang zijn in de compilerbouw, omdat ze sneller te herkennen zijn. Binnen de klasse contextgevoelige talen bestaan ook subtiele subclassificaties, die vooral van belang zijn voor natuurlijketaalverwerking.

Zie ook

• Van Wijngaardengrammatica