Automata, Computability and Complexity

This course introduces three areas of the theory of computation.

First, automata are used to recognize words in (formal) languages, and we will discern several types of languages along with the types of automata that can recognize them.

Second, once we have an intuition about languages, we discuss the topic of computability, where you will learn not only what kinds of problems a computer can solve but also how to prove this.

Third, we will examine the class of computable problems and make a distinction between "easy" and "hard" problems and delve into the famous problem: P = NP?