6 ECTS credits
150 u studietijd
Aanbieding 2 met studiegidsnummer 1007146BNR voor alle studenten in het 2e semester met een verdiepend bachelor niveau.
1. Syntax (formele talen):
1.1. Reguliere talen en eindige automaten: equivalentie, (non)determinisme, optimalizatie.
1.2. Contextvrije grammatica's: definities en algemene eigenschappen (b.v. normaalvormen), stapelautomaten.
1.3. Contextsensitieve grammatica's: definities en algemene eigenschappen, lineair gebonden automaten
1.4. Inleiding tot parsen.
2. Berekenbaarheid: Oplosbare en onoplosbare problemen, Theorema van Church, Turing Machines.
3. Berekenbaarheid in de context van Formele Talen.
Kopieën van de slides, korte samenvattingen van elke les, en gedetailleerde bewijzen zijn beschikbaar op het leerplatform.
Opgelet : De slides en/of samenvattingen zijn op zich geen voldoende studiemateriaal, de slides dienen aangevuld te worden met het verplichte handboek.
Verplicht handboek: Linz: 'An Introduction to Formal Languages and Automata,Jones & Bartlett Learning, 2017.
Aanvullend studiemateriaal:
Inleiding in de theorie van de formele talen,V.J. Rayward-Smith
Berekenbaarheid,V.J. Rayward Smith
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.
De beoordeling bestaat uit volgende opdrachtcategorieën:
Examen Mondeling bepaalt 50% van het eindcijfer
Examen Schriftelijk bepaalt 50% van het eindcijfer
Binnen de categorie Examen Mondeling dient men volgende opdrachten af te werken:
Binnen de categorie Examen Schriftelijk dient men volgende opdrachten af te werken:
50% oefeningen,
50% theorie
Theorie: Er is een verplicht mondeling examen. Het examen is een gesloten boek examen. Om een voldoende te behalen moet een student goed scoren op een 2-tal basisvragen. De bijkomende vragen hebben een hogere moeilijkheidsgraad en bepalen het cijfer.
Oefeningen: Er is een verplicht schriftelijk oefeningenexamen. Dit examen is ook geloten boek.
Beide examens worden afgenomen in de zittijd van het 2de semester.
Deze aanbieding maakt deel uit van de volgende studieplannen:
Bachelor in de ingenieurswetenschappen: elektronica en informatietechnologie Profiel profiel computerwetenschappen
Bachelor in de ingenieurswetenschappen: verkort traject elektronica en informatietechnologie na vooropleiding industriële wetenschappen
Bachelor in de computerwetenschappen: Standaard traject
Bachelor in de wiskunde en Data Science: Standaard traject