Formele taal

Formele talen vormen een zelfstandig onderzoeksgebied binnen de theoretische informatica, formele logica en mathematische taalkunde. In tegenstelling tot de wiskunde worden objecten in formele talen altijd gecodeerd voorgesteld. De natuurlijke getallen zijn bijvoorbeeld voor de wiskunde niet meer dan een gedachtenexperiment; in de theoretische informatica worden zij door codering in het decimale stelsel een formele taal.

Als we de woorden uit een natuurlijke taal als alfabet beschouwen, dan zijn de zinnen binnen deze natuurlijke taal een formele taal over het alfabet van zijn woorden. Bij natuurlijke talen ontbreekt echter een definitie die precies kan bepalen, welke zinnen wel en welke zinnen niet tot de natuurlijke taal behoren (met uitzondering van talen als Latijn en Esperanto). In principe kunnen we stellingen en algoritmen voor formele talen dus enkel voor delen van natuurlijke talen gebruiken.

[bewerk] Definitie

Een formele taal is een verzameling van woorden. Een woord uit een formele taal is een rijtje letters uit het (normaal gesproken eindige) alphabet . Het achter elkaar schrijven van letters of woorden heet concatenatie. Als men deze wil benadrukken wordt meestal of gebruikt. Het maakt niet uit in welke volgorde concatenaties uitgevoerd worden. De volgorde van de letters is echter wel van belang, zodat geldt:

• 

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 . 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 , en (waarbij Σ ^* de taal van alle eindige rijtjes letters uit het alfabet Σ is).

Voorbeeld: Neem Σ = {a,b,c}. Dan is a een woord in Σ ^* . Ook b is een woord in Σ ^* 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 Σ = {α,β,γ}. 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, bijv.: Σ = {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 Σ met een eindige lengte wordt aangeduid met Σ ^* . Zo'n verzameling is dus oneindig groot, maar wel aftelbaar.

Een formele taal L is een deelverzameling van Σ ^* , dus:

[bewerk] Klassen van talen

Er zijn verscheidene klassen van talen, ieder gerelateerd aan een wiskundig model van berekenbaarheid. Al deze talen kunnen omschreven worden door een formele grammatica (regels die aangeven welke woorden tot de taal behoren en welke niet). Bij iedere klasse van taal hoort een klasse van grammatica, waarbij een klasse van grammatica evenveel uitdrukkingskracht bezit als het bijbehorende model van berekenbaarheid (zie complexiteitstheorie). Een veelgebruikte indeling is de Chomskyhiërarchie:

Taalklasse	Model van berekenbaarheid	Grammatica
Regulier	Eindige Automaat	Reguliere grammatica
Contextvrij	Stapelautomaat, ook bekend als push-down automaat	Context-vrije grammatica
Contextgevoelig	Lineair gebonden automaat	Context-gevoelige grammatica
Turingbeslisbaar	Turingmachine	Onbeperkte grammatica
Turingonbeslisbaar	Geen; deze talen zijn onberekenbaar	Geen; onberekenbaar

Merk op dat dit niet de enige mogelijke indeling is; vooral binnen de klasse van context-gevoelige talen zijn subtiele subclassificaties uitgevonden, die vooral van belang zijn voor natuurlijke-taalverwerking.