This topic provides general introduction of the course and a review of related mathematical background and notations that are required to understand the materials in the course.
• Overview of Automata, Complexity and Computability Theories
• Mathematical Preliminaries
Strings and Languages
Problems in modeling of computation are described in terms of strings and languages. This topics provides an introduction to strings and languages and the relationship between them.
• String and its operations
• Language Specification
This topic describes the simplest models of computation and the problems that they can solve which are represented as regular languages.
• Deterministic Finite Automata (DFA)
• Non-deterministic Finite Automata (NFA)
• Regular Languages
Context-free languages represent a set of problems that cannot be solved by finite automaton but can be solved by another model of computation called Push-down automata (PDA). This topic describes how to write grammars of CFG and converting the grammars into normal forms.
• Context-free Grammar (CFG)
• Chomsky and Grebaich Normal Forms
• Push-down Automata (PDA)
This topic describes Turing Machines as model of computation for a general purpose computer. In addition, it also provides the technique to decide whether a problem is solvable by a computer (decidable) or not (undecidable).
• TM Computation
• Decidable vs Undecidable Problems