NWI-IPC002
Talen en Automaten
Cursus informatieRooster
CursusNWI-IPC002
Studiepunten (ECTS)3
CategoriePB (Propedeuse)
VoertaalEngels, Nederlands
Aangeboden doorRadboud Universiteit; Faculteit der Natuurwetenschappen, Wiskunde en Informatica; Informatica en Informatiekunde;
Docenten
VorigeVolgende 1
Docent
dr. M.C. de Bondt
Overige cursussen docent
Docent
prof. dr. J.H. Geuvers
Overige cursussen docent
Docent
dr. A.R.R. Linard
Overige cursussen docent
Contactpersoon van de cursus
dr. J.C. Rot
Overige cursussen docent
Docent
dr. J.C. Rot
Overige cursussen docent
Collegejaar2017
Periode
KW2  (13-11-2017 t/m 04-02-2018)
Aanvangsblok
KW2
Onderwijsvorm
voltijd
OpmerkingVoertaal: Nederlands, tenzij Engels noodzakelijk is.
Inschrijven via OSIRISJa
Inschrijven voor bijvakkersJa
VoorinschrijvingNee
WachtlijstNee
Plaatsingsprocedure-
Cursusdoelen

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

Toetsinformatie
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

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

Werkvormen

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

Verplicht materiaal
Dictaat
Dictaat van Alexandra Silva: "Languages and Automata"
Handouts
Slides van de cursus

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

Werkvormen
Cursusgebeurtenis

Toetsen
Tentamen
Weging1
GelegenhedenBlok KW2, Blok KW4