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 $\backslash mathbb\{N\}=\backslash \{0,1,2,\backslash ldots\backslash \}$ 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 alphabet 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.

Definitie

---

Een formele taal $\backslash mathbf\{\backslash mathit\{L\}\}$ is een verzameling van woorden. Een woord uit een formele taal is een rijtje letters uit het (normaal gesproken eindige) alphabet $\backslash mathbf\{\backslash mathit\{\backslash Sigma\}\}$. Het achter elkaar schrijen van letters of woorden heet concatenatie. Als men deze wil benadrukken wordt meestal $\backslash circ$ of $\backslash cdot$ gebruikt. Het maakt niet uit in welke volgorde concatenaties uitgevoerd worden. De volgorde van de letters is echter wel van belang, zodat geldt:

• $(u\backslash circ\; v)\backslash circ\; w\; =\; u\backslash circ(v\backslash circ\; w)\; =\; uvw$

De concatentatieoperatie is 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 $\backslash 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 $|\backslash varepsilon|\; =\; 0$, $\backslash forall\; a\; \backslash in\; \backslash Sigma\; :\; |a|\; =\; 1$ en $\backslash forall\; v,\; w\; \backslash in\; \backslash Sigma^*\; :\; |v\; \backslash circ\; w|\; =\; |v|\; +\; |w|$ (waarbij $\backslash Sigma^*$ de taal van alle eindige rijtjes letters uit het alfabet $\backslash Sigma$ is).

Voorbeeld: Neem $\backslash Sigma\; =\; \backslash \{a,\; b,\; c\backslash \}$. Dan is a een woord in $\backslash Sigma$. Ook b is een woord in $\backslash 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 vreemde tekens bevatten. Bijvoorbeeld $\backslash Sigma\; =\; \backslash \{\backslash alpha,\; \backslash beta,\; \backslash gamma\backslash \}$. 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.: $\backslash Sigma\; =\; \backslash \{0,\; 1,\; 2,\; 3,\; 4,\; 5,\; 6,\; 7,\; 8,\; 9,\; 10,\; 11,\; 12\backslash \}$. 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 $\backslash Sigma$ met een eindige lengte wordt aangeduid met $\backslash Sigma^*$. Zo'n verzameling is dus oneindig groot, maar wel aftelbaar.

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

$L\_\{\backslash Sigma\}\; \backslash subseteq\; \backslash Sigma^*$

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). Over het algemeen onderscheiden we de volgende klassen van talen:

Taalklasse	Model van berekenbaarheid	Grammatica
Regulier	Eindige Automaat	Reguliere grammatica
Context-vrij	Stapelautomaat, ook bekend als push-down automaat	Context-vrije grammatica
Context-gevoelig	Lineair gebonden automaat	Context-gevoelige grammatica
Turing-beslisbaar	Turingmachine	Onbeperkte grammatica
Turing-onbeslisbaar	Geen; deze talen zijn onberekenbaar	Geen; onberekenbaar

Dit is de zgn. Chomsky-hiërarchie. 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.

Theoretische informatica | Soort taal | Formele wetenschap

Формален език | Formální jazyk | Formale Sprache | Formal language | Lenguaje formal | Formaali kieli | Langage formel | Linguaggio formale (matematica) | 形式言語 | 형식 언어 | Język formalny | Linguagem formal | Limbaje formale | Формальный язык | Formálny jazyk | Biçimsel dil kuramı | 形式语言