Automaten en berekenbaarheid

Professor
Bart Bogaerts
Course description
Inhoud:
  • Syntax (formele talen):

    Reguliere talen en eindige automaten: equivalentie, (non)determinisme, optimalizatie.
    Contextvrije grammatica’s: definities en algemene eigenschappen (b.v. normaalvormen), stapelautomaten.
    Contextsensitieve grammatica’s: definities en algemene eigenschappen, lineair gebonden automaten 
    Inleiding tot parsen.

  • Berekenbaarheid: Oplosbare en onoplosbare problemen, Theorema van Church, Turing Machines.

  • Berekenbaarheid in de context van Formele Talen. 

Leerresultaten:
  • Herinneren:
    De student kan basisbegrippen uit de cursus (zoals: reguliere talen, contextvrije talen, eindige (niet-)deterministische accepters, Turing machines, contextsensitieve grammaticas, …) definiëren. 

  • Begrijpen: 
    De student kan redeneren over de mogelijkheden en de beperkingen van formele talen zoals reguliere, context-vrije en contextsensitieve talen en de corresponderende automaten voor deze talen.
    De student kan de basisbegrippen van de theorie van berekenbaarheid uitleggen. 
    De student kan de geziene bewijzen herconstrueren en mondeling toelichten.

  • Toepassen:
    De student kan de geziene stellingen en technieken toepassen op nieuwe talen/automaten/grammaticas.

  • Analyseren & Evalueren:
    De student kan ongeziene formele talen classificeren in de Chomsky hierarchie en zijn/haar classificatie beargumenteren 
    De student kan evalueren of een ongezien probleem tot de klasse van de (semi-)beslisbare of (semi-)berekenbare problemen behoort en zijn/haar oordeel beargumenteren.
    De student kan correcte wiskundige redeneringen opstellen en foutieve wiskundige redeneringen analyseren en identificeren. 

  • Creëren:
    De student kan een wiskundig correct bewijs opstellen voor varianten van geziene eigenschappen. 
    De student kan een automaat/grammatica opstellen die een gegeven formele taal accepteert. 

All detailed and official information about the course here >