Formele talen en automaten

Talen kunnen natuurlijke talen zijn (Nederlands, Engels), maar evengoed programmeertalen zoals de taal Java. Wie een zin uit bijvoorbeeld het Nederlands wil vertalen in een andere taal, zoals het Engels, heeft een grondige kennis nodig van zowel de structuur (syntaxis) als de betekenis (semantiek) van de twee talen. Als een vertaling door een computer moet worden uitgevoerd, dan moeten de syntaxis en semantiek op de een of andere manier formeel worden vastgelegd. Dat is voor natuurlijke talen een zeer lastige zaak. Formele talen, zoals programmeertalen, hebben een veel eenvoudigere structuur, die geautomatiseerd kan worden gecontroleerd. Die structuur wordt vastgelegd in een grammatica of in een automaat.

In deze cursus komen verschillende soorten formele talen met de bijbehorende grammatica's en automaten aan de orde. Ook wordt aandacht besteed aan het zelf ontwerpen van deze grammatica's en automaten.
Het eerste blok vormt een algemene inleiding op formele talen.
In het tweede blok worden de eigenschappen van reguliere talen en van eindige automaten behandeld. Contextvrije talen en stapelautomaten zijn het onderwerp van blok drie. In het laatste blok komen Turingmachines, de Chomsky-hiërarchie en de begrippen beslisbaarheid en complexiteit van problemen aan de orde.