Lesson 1
Introduction
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
Lesson 2
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
Lesson 3
Finite Automata
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
Lesson 4
Context-Free Grammar
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)
Lesson 5
Turing Machine
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
• Algorithm
• Decidable vs Undecidable Problems