NWI-IPC002
Languages and Automata
Cursus informatieRooster
CursusNWI-IPC002
Studiepunten (ECTS)3
CategorieBA (Bachelor)
VoertaalEngels
Aangeboden doorRadboud Universiteit; Faculteit der Natuurwetenschappen, Wiskunde en Informatica; Informatica en Informatiekunde;
Docenten
Docent
prof. dr. J.H. Geuvers
Overige cursussen docent
Examinator
dr. J.C. Rot
Overige cursussen docent
Docent
dr. J.C. Rot
Overige cursussen docent
Coördinator
dr. J.C. Rot
Overige cursussen docent
Contactpersoon van de cursus
dr. J.C. Rot
Overige cursussen docent
Collegejaar2019
Periode
KW3  (03-02-2020 t/m 12-04-2020)
Aanvangsblok
KW3
Onderwijsvorm
voltijd
Opmerking-
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. 
Niveau

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.
  • Toetsinformatie
    The final grade is based on:
  • weekly homework assignments (h),
  • final exam (t) Homework qualifies as a potential bonus for the final grade, which is t + h/10, provided that t >= 5.
  • Bijzonderheden

    Onderwerpen
    • Words, languages, structural induction, 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)

    Homework qualifies as a potential bonus for the final grade, which 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
    ToetsvormDigitale toets met CIRRUS
    GelegenhedenBlok KW4, Blok KW4