|
|
|
|
|
Formal Languages and Formal Grammars arise from the need to formalize the informal notions of grammar and language. Many formal grammars were invented: right-linear grammars, context-free grammars and unrestricted grammars. These grammars can be placed in a natural hierarchy. The goal of this course is to begin understanding the foundations of computation. Various models of computation exist, all of which capture some fundamental aspect of computation. We concentrate on three classes of models: models with finite amount of memory (finite-state automata); models with stack memory (push-down automata); and unrestricted models (Turing machines). Surprisingly, there is a deep connection between these grammars, the strings they generate (their language), and the models of computation introduced above. This course also briefly covers the impact of formal language theory for many computer science applications: in compilers, natural language processing, and program verification.
Although announced as part two, there have not been part one and the course will try to be interesting not only for beginners but also for a bit advanced students.There are no special prerequisites in terms of specific courses to attend. Students are expected to be familiar with the basic notions of mathematics and with basic proof techniques, as taught in the mathematics courses of the first year.
Winter Semester 2019.
Please register for the course via the KUSSS system.
Maintained by Nikolaj Popov