Skip to main content
B.Sc. DegreeFaculty of Faculty of Computing & Information TechnologyComputer Science

Theory of Computation

Master Theory of Computation in University - Computer Science with this structured course, covering 8 modules and practice assessments.

Instructor
Created by PAMCET Learning Team
intermediate2 - 4 weeksEnglish

Course Overview

Master Theory of Computation in University - Computer Science with this structured course, covering 8 modules and practice assessments. Curriculum Structure & Core Modules: • 1. Introduction to Formal Languages, Automata Theory & Mathematical Foundations • 2. Deterministic &...

What You'll Learn

  • Understand and apply the principles of Finite Automata
  • Work confidently through Regular Expressions and Languages and its practical applications
  • Analyse real-world scenarios involving Context-Free Grammars
  • Develop applied skills in Pushdown Automata
  • Critically evaluate approaches to Turing Machines

Requirements

  • A foundational understanding of University - Computer Science concepts, from an introductory course or equivalent experience
  • A computer, tablet or smartphone with a stable internet connection
  • Willingness to commit regular study time to complete lessons, quizzes and assignments

Degree Programme Curriculum Context

This course is a curriculum unit of the B.Sc. Computer Science degree framework in Nigeria.

Earn Your Certificate

Showcase your skills with a certificate! Complete the course, submit your project, and earn your certificate. Here's a sample of what you'll receive to show off your accomplishments.

course-certificate
Lecture Board & Syllabus

Course Curriculum

Browse complete theoretical foundations, worked calculations, laboratory protocols, and board assessment questions under each topic.

Launch Course Reader →
8 Chapters
•
24 Lecture
•
18h
Subtopic 1Document LectureOpen Access

Mathematical Foundations: Sets, Alphabets, Strings, Formal Languages & Operations

Sign in or enroll to access the full lecture notes and interactive reader.

Module 1 • Subtopic 1
Subtopic 2Document Lecture

Inductive Proof Techniques: Mathematical Induction, Structural Induction & Invariants

Sign in or enroll to access the full lecture notes and interactive reader.

Module 1 • Subtopic 2
Subtopic 3Document Lecture

Foundations of Automata Theory: State Transitions, Transition Graphs & Computation Models

Sign in or enroll to access the full lecture notes and interactive reader.

Module 1 • Subtopic 3
Subtopic 1Document Lecture

Deterministic Finite Automata (DFA): Formal Definition, State Diagrams & Extended Transition Functions

Sign in or enroll to access the full lecture notes and interactive reader.

Module 2 • Subtopic 1
Subtopic 2Document Lecture

Nondeterministic Finite Automata (NFA): Formal Definition, Epsilon-Transitions & Branching Semantics

Sign in or enroll to access the full lecture notes and interactive reader.

Module 2 • Subtopic 2
Subtopic 3Document Lecture

Equivalence of DFA and NFA: The Subset (Powerset) Construction & Computational Equivalence

Sign in or enroll to access the full lecture notes and interactive reader.

Module 2 • Subtopic 3
Subtopic 1Document Lecture

Regular Expressions: Formal Syntax, Inductive Semantics & Language Specification

Sign in or enroll to access the full lecture notes and interactive reader.

Module 3 • Subtopic 1
Subtopic 2Document Lecture

Kleene's Theorem: Equivalence of Regular Expressions and Finite Automata via GNFA Elimination

Sign in or enroll to access the full lecture notes and interactive reader.

Module 3 • Subtopic 2
Subtopic 3Document Lecture

Myhill-Nerode Theorem, Equivalence Relations & Hopcroft's DFA State Minimization Algorithm

Sign in or enroll to access the full lecture notes and interactive reader.

Module 3 • Subtopic 3
Formative Assessment10 Points • 15 Mins

Mid-Course Progress Assessment

Assessment Protocol:10 Total Points•70% Passing Threshold•15 Mins Time Limit•Bloom's Taxonomy: Analyze & Evaluate

Test your knowledge of Pushdown Automata

Module 4 • Formative Assessment
Subtopic 2Document Lecture

The Pumping Lemma for Regular Languages: Adversarial Formulation & Formal Proofs

Sign in or enroll to access the full lecture notes and interactive reader.

Module 4 • Subtopic 2
Subtopic 3Document Lecture

Proving Non-Regularity: Pumping Lemma Applications & Information-Theoretic Lower Bounds

Sign in or enroll to access the full lecture notes and interactive reader.

Module 4 • Subtopic 3
Subtopic 4Document Lecture

Closure Properties and Decision Algorithms for Regular Languages

Sign in or enroll to access the full lecture notes and interactive reader.

Module 4 • Subtopic 4
Subtopic 1Open Access~3 min read

Mid-Semester Case Study & Research Paper

Sign in or enroll to access the full lecture notes and interactive reader.

Module 5 • Subtopic 1•109 characters of authentic academic content
Subtopic 2Document Lecture

Context-Free Grammars: Formal 4-Tuple Specification, Derivations & Language Generation

Sign in or enroll to access the full lecture notes and interactive reader.

Module 5 • Subtopic 2
Subtopic 3Document Lecture

Parse Trees, Yield of a Tree, Structural Ambiguity & Inherently Ambiguous Languages

Sign in or enroll to access the full lecture notes and interactive reader.

Module 5 • Subtopic 3
Subtopic 4Document Lecture

Chomsky Normal Form (CNF) & The CYK Parsing Algorithm

Sign in or enroll to access the full lecture notes and interactive reader.

Module 5 • Subtopic 4
Subtopic 1Document Lecture

Pushdown Automata (PDA): Formal 6-Tuple Definition, Stack Dynamics & Acceptance Modes

Sign in or enroll to access the full lecture notes and interactive reader.

Module 6 • Subtopic 1
Subtopic 2Document Lecture

Equivalence of Context-Free Grammars and Pushdown Automata

Sign in or enroll to access the full lecture notes and interactive reader.

Module 6 • Subtopic 2
Subtopic 3Document Lecture

Pumping Lemma for Context-Free Languages, Ogden's Lemma & CFL Closure Properties

Sign in or enroll to access the full lecture notes and interactive reader.

Module 6 • Subtopic 3
Subtopic 1Document Lecture

Turing Machines: Formal 7-Tuple Definition, Tape Operations & Instantaneous Descriptions

Sign in or enroll to access the full lecture notes and interactive reader.

Module 7 • Subtopic 1
Subtopic 2Document Lecture

Turing Machine Variants & Computational Equivalence

Sign in or enroll to access the full lecture notes and interactive reader.

Module 7 • Subtopic 2
Subtopic 3Document Lecture

The Church-Turing Thesis, Alternative Models of Computation & The Chomsky Hierarchy

Sign in or enroll to access the full lecture notes and interactive reader.

Module 7 • Subtopic 3
Formative Assessment10 Points • 15 Mins

Comprehensive End-of-Course Examination

Assessment Protocol:10 Total Points•70% Passing Threshold•15 Mins Time Limit•Bloom's Taxonomy: Analyze & Evaluate

Test your knowledge of P vs NP Problem

Module 8 • Formative Assessment
Subtopic 2Document Lecture

Decidable vs Recognizable Languages: Universal Turing Machine & The Acceptance Problem A_TM

Sign in or enroll to access the full lecture notes and interactive reader.

Module 8 • Subtopic 2
Subtopic 3Document Lecture

Undecidability of the Halting Problem & Mapping Reductions

Sign in or enroll to access the full lecture notes and interactive reader.

Module 8 • Subtopic 3
Subtopic 4Document Lecture

Rice's Theorem, Post's Correspondence Problem (PCP) & Computation Limits

Sign in or enroll to access the full lecture notes and interactive reader.

Module 8 • Subtopic 4

Instructor

PAMCET Learning Team

PAMCET Learning Team

Institutional Course Curation · PAMCET

The PAMCET Learning Team is the institutional curriculum and content group behind course publishing on this platform. PAMCET (Professional and Academic Management Centre for Education and Training) is operated by Digitpen Hub Ltd, a company registered in Lagos, Nigeria. Courses credited to the PAMCET Learning Team are structured, organized, and published centrally by the platform rather than authored by a single named individual instructor — each course's syllabus, learning outcomes, and content are reviewed before publication under this institutional account. For questions about a specific course or to report a content issue, please use the platform's Help & Support or Contact Us pages.

Qualifications:

PAMCET Learning Team — Institutional Course Curation, Digitpen Hub Ltd

My Skills:

  • Curriculum Curation
  • Course Content Review
  • Learning Outcome Design
  • Course Publishing & Quality Assurance
  • Platform Content Operations

Reviews

No reviews available
Theory of Computation
Free$24.99100% Off
Certificate available separately for $7 after completion

Course Includes

8 Chapters
24 Lectures
2 - 4 weeks
Skill Level intermediate
Taught in English
Lifetime Access
Certification of Completion
Category: University - Computer Science
Share On

Download Syllabus & Study Guide

Receive the full lecture syllabus, reading list, and milestone schedule for Theory of Computation.

By submitting, you agree to receive educational updates. You can unsubscribe anytime. Read our Privacy Policy.

Theory of Computation — B.Sc. | PAMCET