uCertify

Theory of Computation: Automata, Formal Languages, Computation and Complexity

(THEORY-CMPUTATION.AU1)
Lessons
Lab
AI Tutor (Add-on)
Get A Free Trial

Skills You’ll Get

Download Course Outline

1

Introduction

  • Significance of Theory
  • Background and Motivation
  • The Scope, Organization, and Approach
2

Mathematical Preliminaries

  • Introduction
  • Set Theory
  • Theorems and Proofs
  • Russell’s Paradox and Cantor’s Diagonal Argument
  • Set Relations
  • Functions
  • Graph Theory
  • Algebraic Theory of Machines
  • Operations on Strings
  • Strings and Languages
  • Closure Properties of Languages
  • Representation of Languages
  • Summary
3

Finite Automata and Regular Expressions

  • Introduction
  • Automata Theory
  • Modeling of Programs and Computation
  • Finite Automata Model
  • Regular Expressions
  • Applications of Finite Automata
  • Automata Concepts Through Games
  • Summary
4

Variants of Finite Automata

  • Introduction
  • Nondeterministic Finite Automata Model
  • Properties of NFA
  • Equivalence of NFA and DFA
  • Two-way Finite Automata
  • Finite Automata with Output
  • Equivalence of Moore and Mealy Machines
  • Finite-State Transducers
  • Summary
5

Minimization of Finite Automata

  • Introduction
  • From Regular Expression to DFA
  • Formalism for Minimization
  • Minimization of Finite Automata
  • NFA Homomorphism
  • State Minimization Based on Equivalence Classes
  • Myhill–Nerode Theorem
  • Partitioning State Space
  • Partition-Refine Algorithm
  • Table-filling Algorithm
  • Equivalences of Regular Expressions
  • Summary
6

Regular Languages

  • Introduction
  • Regular Languages
  • Closure Properties of Regular Languages
  • On Regularity of Languages
  • DFA to Regular Expression
  • Pumping Lemma for Regular Languages
  • On Nonregularity of Languages
  • Myhill–Nerode Theorem and Its Applications
  • Regular Expression to DFA Using MN
  • Summary
7

Context-Free Grammars and Languages

  • Introduction
  • Context-Free Grammars
  • Relation Between FA and Regular Grammars
  • Derivation of Sentences
  • Closure Properties of Context-Free Languages
  • Parsing Context-Free Languages
  • Parsing Arithmetic Expressions
  • Ambiguous Grammars and Languages
  • Disambiguating Ambiguous Grammars
  • Operator-Precedence Grammars
  • Classifying Context-Free Grammars
  • Invertible Grammars
  • Summary
8

Normal Forms of Context-Free Grammars

  • Introduction
  • Simplification of Grammars
  • Chomsky Normal Form
  • Greibach Normal Form
  • Converting CNF to GNF Grammar
  • Complexity Analysis of GNF Grammar
  • Pumping Lemma for Context-Free Languages
  • Decidable Properties of Context-Free Languages
  • Summary
9

Pushdown Automata and Parsers

  • Introduction
  • The Idea of Parsing
  • Pushdown Automata Model
  • Formalism of PDA
  • Pushdown Automata Simulation
  • Types of PDAs
  • Language Acceptability by PDA
  • Equivalence of PDA and Context-Free Grammar
  • Parsers
  • LL(k) and LR(k) Grammars
  • LL Parser
  • LR Parser
  • Parallelization
  • Summary
10

Turing Machine and Computability

  • Introduction
  • Algorithmic Complexity
  • Analysis of Human Computation
  • Turing Machine Model
  • Language Recognition by Turing Machine
  • Turing Machines and Formal Languages
  • Computability
  • Church-Turing Thesis
  • Post Machine
  • Turing Machine Simulation
  • Computing Beyond the Turing Limit
  • Summary
11

Extensions of Basic Turing Machine

  • Introduction
  • Multi-tape Turing Machine
  • Linear Speedup
  • Multiple-track Turing Machine
  • Nondeterministic Turing Machine
  • Turing Machine and Type-0 Grammars
  • Universal Turing Machine
  • The Halting Problem of TM
  • Modern Computer Simulation on Turing Machine
  • Computing Frameworks
  • Summary
12

Linear-Bounded Automata and Context-Sensitive Languages

  • Introduction
  • Linear-Bounded Automata Model
  • Language Acceptability by LBA
  • Context-Sensitive Grammars and Languages
  • Non-context-free Properties of Programming Languages
  • Chomsky-Hierarchy Grammars and Languages
  • Closure Properties of Context-Sensitive Languages
  • Indexed Grammars
  • Regulated Rewriting Grammars
  • Conjunctive Grammars
  • Universal Versus Chomskian Grammars
  • Summary
13

Decidability, Undecidability, and Unsolvability

  • Introduction
  • Recursive and Recursive Enumerable Sets
  • Computable Sets
  • Recursive and Recursively Enumerable Languages
  • Decision Problems
  • Some Standard Problems and Their Intuitive Algorithms
  • Decidable Properties of Grammars and Languages
  • Enumeration of Languages and Turing Machines
  • Gödel Numbering
  • Unsolvability
  • Undecidability
  • Undecidability of Halting Problem
  • Rice’s Theorem
  • Summary
14

Computational Complexity Theory

  • Introduction
  • Determining Time Complexity
  • Time Complexity of Arithmetic Operations
  • Multi-tape Turing Machine Complexity
  • Concepts of Time and Space Complexities
  • Computational Complexity
  • Time- and Space-Bounded Complexities
  • Time-Bounded Complexity Classes
  • Space-Bounded Complexity Classes
  • Canonical Complexity Classes
  • Circuit Complexity
  • Reducibility
  • Primality and Compositness
  • Summary
15

NP-Completeness

  • Introduction
  • Class NP
  • Boolean Satisfiability
  • Cook–Levin Theorem
  • NP-Completeness
  • NP-Complete Problems
  • Solving SAT Problems
  • Counting Problems
  • Summary

Related Courses

All Courses