NWI-IPC002
Languages and Automata
Course infoSchedule
Course moduleNWI-IPC002
Credits (ECTS)3
CategoryPB (Propaedeutic)
Language of instructionDutch, English
Offered byRadboud University; Faculty of Science; Informatica en Informatiekunde;
Lecturer(s)
PreviousNext 1
Lecturer
dr. M.C. de Bondt
Other course modules lecturer
Lecturer
prof. dr. J.H. Geuvers
Other course modules lecturer
Lecturer
dr. A.R.R. Linard
Other course modules lecturer
Contactperson for the course
dr. J.C. Rot
Other course modules lecturer
Lecturer
dr. J.C. Rot
Other course modules lecturer
Academic year2017
Period
KW2  (13/11/2017 to 04/02/2018)
Starting block
KW2
Course mode
full-time
RemarksLanguage of instruction: Dutch, unless English is required.
Registration using OSIRISYes
Course open to students from other facultiesYes
Pre-registrationNo
Waiting listNo
Placement procedure-
Aims

Aan het einde van deze cursus kunnen de studenten

  • talen karakteriseren via reguliere expressies, automaten 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.
Content
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.
Literature
Dictaat van Alexandra Silva (beschikbaar via de website van de cursus): "Languages and Automata",Slides van de cursus (beschikbaar via de website van de cursus)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.

Teaching formats

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

Topics
• 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
• Toepassingen: alternatieve beschrijvingen, parseren

Test information
De beoordeling is gebaseerd op drie resultaten:

• de huiswerk opdrachten (h),
• een schriftelijk deeltentamen over het onderdeel reguliere talen (t1),
• een schriftelijk deeltentamen over het onderdeel contextvrije talen (t2).

Het eindcijfer voor Talen en Automaten is (t1+t2)/2 + h/10 mits:
• beide deeltentamencijfers >= 5 zijn
• het huiswerkcijfer >= 5 is

Prerequisites
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.

Required materials
Reader
Lecture notes by Alexandra Silva: "Languages and Automata"
Handouts
Lecture slides

Recommended materials
Book
T.A. Sudkamp, Languages and Machines: An introduction to the theory of computer science, Third Edition, Pearson/Addison Wesley, Boston etc.

Instructional modes
Course occurrence

Tests
Tentamen
Test weight1
OpportunitiesBlock KW2, Block KW4