Senior Lecturer at Computer Science and Software Engineering Division Mälardalen University

Formal Languages, Automata and Theory of Computation

Undergraduate course, 7.5 credits, Mälardalen University, Computer Science and Software Engineering Department, 1900

Formal Languages, Automata and Theory of Computation provides an insight into theoretical foundations of artificial languages, automata and theory of computation - topics that appear in various disguises in every branch of computer science.

Learning outcomes

After completing the course the student shall be able to:

  1. show basic theoretical knowledge, both regarding the connection between grammars, automata and languages and regarding fundamental limitations of computation,
  2. apply practical knowledge, both the ability to construct and simulate formal machines and grammars, and
  3. demonstrate the ability to reflect in writing on the course content in relation to different computational paradigms.

Course content Regular languages and Finite automata. Context-free languages and Pushdown automata. Recursively enumerable languages and Turing machines. The Universal Turing machine. Decidability - Stop problem. Computing paradigms.