Formele taal (theoretische informatica)

In de theoretische informatica en wiskunde is een formele taal een verzameling van strings die gevormd worden uit symbolen uit een eindig alfabet. De elementen van deze verzameling zijn de syntactisch correcte uitdrukkingen van de taal. De betekenis van deze tekenreeksen (de semantiek) wordt buiten beschouwing gelaten. Formele talen kunnen op verschillende manieren worden beschreven, bijvoorbeeld met grammatica's.

Achtergrond

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.

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 ${\displaystyle \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.

Een taal wordt in de formeletalentheorie gedefinieerd als een verzameling eindige tekenreeksen bestaande uit tekens gekozen uit een gegeven eindig alfabet. Met elke taal is een predicaat geassocieerd, namelijk het predicaat dat van elke tekenreeks bepaalt of het tot de taal behoort of niet.

De theorie beschrijft en bestudeert mechanismen waarmee talen gedefinieerd kunnen worden. Voorbeelden van zulke mechanismen zijn grammatica's en automaten; van beide bestaan allerlei soorten. Ook expressies worden gebruikt, bijvoorbeeld reguliere expressies.

Het blijkt dat lang niet alle mechanismen dezelfde uitdrukkingskracht hebben: sommige talen kunnen wel met het ene en niet met het andere mechanisme worden beschreven. Zo kunnen allerlei verschillende klassen talen onderscheiden worden aan de hand van de mechanismen waarmee ze beschreven kunnen worden. Een reguliere taal is bijvoorbeeld een taal die kan worden beschreven door een reguliere expressie.

De theorie is ontstaan in de jaren vijftig met als doel een wiskundige basis te geven voor de beschrijving van machines die ingewikkelde tekenreeksen moeten herkennen en verwerken.

Men kan zich bijvoorbeeld afvragen wat er nodig is om een machine een natuurlijke taal zoals het Engels of het Nederlands te laten herkennen. Alle woorden en alle zinnen in de taal (alle grammaticale zinnen) kan beschouwd worden als tekenreeksen over het alfabet waar de taal mee wordt geschreven, plus eventueel interpunctie; dus als een formele taal in bovengenoemde zin. Een interessante vraag is dan wat voor wiskundig beschrijvingsmechanisme geschikt is om een natuurlijke taal mee te beschrijven.

Noam Chomsky volgde deze aanpak. Hij hoopte een eenvoudig formalisme te vinden dat geschikt is om precies het soort taal te beschrijven waar bestaande natuurlijke talen voorbeelden van zijn. Reguliere expressies zijn niet krachtig genoeg; daarom kwam hij met verschillende soorten grammatica's; waarvan de contextvrije grammatica redelijk voldoet, maar toch niet krachtig genoeg is, terwijl de andere soorten hun eigen nadelen hebben. Voor de meeste talen zijn er uitgebreide grammatica's die de zinnen in de taal 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. Ook bleek het erg moeilijk om het juiste beschrijvingsformalisme te vinden; met zijn grammatica's 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 gesteld worden, of zelfs helemaal niet gesteld worden.

Definitie

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

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

maar

${\displaystyle \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.

Notatie

De concatenatieoperator wordt meestal niet geschreven: ${\displaystyle u\circ v\circ w}$ wordt meestal geschreven als uvw.

Men geeft het lege woord, een rij zonder enige letter, meestal aan met ${\displaystyle \varepsilon }$.

Het alfabet van een gegeven taal wordt meestal genoteerd als ${\displaystyle \Sigma }$. De kleinste taal over dit alfabet is de lege verzameling ${\displaystyle \emptyset }$, met 0 elementen; de grootste is de verzameling van alle eindige tekenreeksen over ${\displaystyle \Sigma }$, die genoteerd wordt als ${\displaystyle \Sigma ^{*}}$. Voor elke taal ${\displaystyle L}$ met alfabet ${\displaystyle \Sigma }$ geldt: ${\displaystyle L\subseteq \Sigma ^{*}}$.

Een tekenreeks (string) is altijd eindig, maar een taal hoeft dat niet te zijn; wel is een taal altijd aftelbaar.

Als ${\displaystyle w}$ een woord is, dan wordt met ${\displaystyle |w|}$ de lengte daarvan bedoeld, dus het aantal letters in de reeks.

We hebben ${\displaystyle |\varepsilon |=0}$, ${\displaystyle \forall a\in \Sigma$ :|a|=1} en ${\displaystyle \forall v,w\in \Sigma ^{*}:|v\circ w|=|v|+|w|}$.

Voorbeelden

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

Voorbeelden van talen met alfabet ${\displaystyle \Sigma }$:

• ${\displaystyle \emptyset }$
• ${\displaystyle \{\varepsilon \}}$
• ${\displaystyle \Sigma }$
• ${\displaystyle \Sigma ^{*}}$
• ${\displaystyle \{\varepsilon ,a,ab,aabbc,ababacacbacabbc\}}$
• alle tekenreeksen die evenveel a's als b's bevatten en geen andere tekens.

Een alfabet kan behalve tekens in het Romeinse alfabet allerlei andere tekens bevatten. Voorbeelden:

• ${\displaystyle \Sigma =\{\alpha ,\beta ,\gamma \}}$.
• Neem als tekens de Belgische verkeersborden en als taal de mogelijke reeksen verkeersborden die men achtereenvolgens kan tegenkomen bij een autorit door België.
• Neem als tekens de mogelijke zetten in het schaakspel en als taal de verzameling geldige schaakpartijen.
• Probeer de zang van bijvoorbeeld de nachtegaal te analyseren als bestaande uit een opeenvolging van een eindig aantal verschillende soorten fragmenten. Stel dat dit lukt. De soorten zijn dan het alfabet; de taal is de mogelijke zang die een nachtegaal daaruit produceert.

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: ${\displaystyle \Sigma =\{0,1,2,3,4,5,6,7,8,9,10,11,12\}}$. Een woord (of zin) is dan een reeks getallen.

Klassen van talen

Zoals al genoemd heeft Noam Chomsky verschillende soorten grammatica's beschreven. Die zijn te ordenen aan de hand van hun uitdrukkingskracht; het resultaat is de chomskyhiërarchie, die talen indeelt in klassen. 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.