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