NWI-IPC002
Languages and Automata
Cursus informatieRooster
CursusNWI-IPC002
Studiepunten (ECTS)3
CategoriePB (Propedeuse)
VoertaalEngels
Aangeboden doorRadboud Universiteit; Faculteit der Natuurwetenschappen, Wiskunde en Informatica; Informatica en Informatiekunde;
Docenten
Coördinator		dr. J.C. Rot
Overige cursussen docent
Docent		dr. J.C. Rot
Overige cursussen docent
Contactpersoon van de cursus		dr. J.C. Rot
Overige cursussen docent
Examinator		dr. J.C. Rot
Overige cursussen docent
Collegejaar2018
Periode
KW2  (05-11-2018 t/m 27-01-2019)
Aanvangsblok
KW2
Onderwijsvorm
voltijd
OpmerkingAs of 2018, this course is taught in English.
Inschrijven via OSIRISJa
Inschrijven voor bijvakkersJa
VoorinschrijvingNee
WachtlijstNee
Plaatsingsprocedure-
Cursusdoelen
By the end of this course, the students can
  • recognise and describe languages using various kinds of automata, grammars, regular expressions and set-theoretic descriptions
  • carry out basic constructions on automata and expressions, including constructions to convert between different descriptions of regular and context-free languages
  • classify languages in the Chomsky hierarchy
  • define and reason about languages and words using structural induction
Inhoud
In this course, you learn to accurately and formally describe (computer) languages, and mechanisms to check whether a given word/text is a member of such a language. You learn about different classes of languages, and ways to describe these with mathematical models. Aspects of this course occur throughout computer science, for example in the design of programming languages, in (network) protocols, text processing, program verification, and in compiler construction. 
Onderwerpen
• Words, languages, classes of languages; the Chomsky hierarchy
• Regular languages: regular expressions, regular grammars, finite automata, proving non-regularity
• Context-free languages: grammars, normal forms, pushdown automata

Toetsinformatie
The final grade is based on:

• weekly homework assignments (h),
• final exam (t)

The final grade is t + h/10, provided that t >= 5.

Voorkennis
The students can
• explain mathematical definitions in terms of sets, relations and functions
• apply elementary proof techniques for these structures
• prove properties of natural numbers using induction
It suffices to succesfully complete the course Mathematical Structures.

Verplicht materiaal
Dictaat
Lecture notes by Alexandra Silva: "Languages and Automata"
Handouts
Lecture slides

Aanbevolen materiaal
Boek

Werkvormen
Cursusgebeurtenis

Opmerking
• 14 hours lecture
• 14 hours exercise class
• 56 hours self study

Toetsen
Tentamen
Weging1
ToetsvormTentamen
GelegenhedenBlok KW2, Blok KW3