Computatietheorie

Computatietheorie — helder, compact en praktisch. Dit boek leidt u stap voor stap in de basisprincipes van formele talen en berekenbaarheid: van eindige automaten via pushdown-automaten en contextvrije grammatica’s tot de krachtige Turingmachine. U leert niet alleen de formele modellen kennen, maar begrijpt ook de bewijstechnieken waarmee eigenschappen van talen aangetoond worden — en vooral waar de grenzen van het berekenbare liggen. Met talrijke voorbeelden, duidelijke grafieken, overzichtelijke bewijzen en oefenopgaven met voorbeeldantwoorden is dit boek ideaal voor studenten, docenten en iedereen die zich gestructureerd in het onderwerp wil verdiepen. Kernbegrippen zoals het pumping-lemma, Myhill–Nerode, de stelling van Kleene, evenals diagonalisatie en de stelling van Rice, worden begrijpelijk gepresenteerd en in hun consequenties besproken. Er is bijzondere aandacht besteed aan begrijpelijkheid en praktische bruikbaarheid: de hoofdstukken zijn modulair opgebouwd, bewijzen volledig uitgewerkt, en waar technische details afleiden, wordt de intuïtie benadrukt. Talrijke oefenopgaven bevorderen actief begrip — perfect als begeleidend tekstmateriaal bij colleges of voor zelfstudie.