Talen en automaten

Inleiding

In deze cursus maak je kennis met methoden om een (computer)taal heel precies te beschrijven en met mechanismen om na te gaan of een gegeven tekst tot die taal behoort. Je past deze methoden toe op een voorbeeld uit de praktijk.
Aspecten van deze cursus kom je overal tegen in de informatica, bijvoorbeeld bij het ontwerp van programmeer- en specificatietalen en bij de constructie van vertalers (compilers) en gebruikersinterfaces.

Leerdoelen

Aan het einde van deze cursus kunnen de studenten
  • talen karakteriseren via reguliere expressies en grammatica's;
  • bij een gegeven taal een herkennende automaat construeren;
  • eigenschappen van talen onderzoeken aan de hand van beschrijvingen en automaten;
  • een gegeven taal classificeren in de talenhiërarchie.

Onderwerpen

  • Woorden, talen, klassen van talen; de Chomsky hiërarchie in het kort
  • Reguliere talen: reguliere expressies, reguliere grammatica's, eindige automaten, pomplemma
  • Contextvrije talen: contextvrije grammatica's, standaardvormen, stapelautomaten, pomplemma
  • Toepassingen: alternatieve beschrijvingen, parseren

Werkvormen

  • 16 uur hoorcollege
  • 16 uur werkcollege
  • 52 uur zelfstudie

Toetsvorm

De beoordeling is gebaseerd op drie resultaten:

  • de huiswerk opdrachten, 
  • een schriftelijk deeltentamen over het onderdeel reguliere talen,
  • een schriftelijk deeltentamen over het onderdeel contextvrije talen.
Het eindcijfer voor Talen en Automaten is het gewogen gemiddelde van deze drie resultaten, mits beide deeltentamencijfers > 5 zijn.

Vereiste voorkennis

De studenten kunnen
  • wiskundige definities in termen van verzamelingen, relaties en functies uitleggen;
  • elementaire bewijsmethoden voor deze structuren toepassen;
  • eigenschappen voor natuurlijke getallen bewijzen met behulp van volledige inductie.
Hiervoor volstaat het succesvol doorlopen van de cursus Wiskundige Structuren.

Literatuur

T.A. Sudkamp, Languages and Machines: An introduction to the theory of computer science, Third Edition, Pearson/Addison Wesley, Boston etc., 2006. ISBN 0-321-31534-0.

Bijzonderheden

De cursus zal in het Engels gegeven worden.

Website


Vakcode
NWI-IPC002
Studiepunten
3 ec
Periode
tweede kwartaal

Docenten

Opgenomen in

  • Bachelor Informatica