THEORY OF COMPUTATION

THEORY OF COMPUTATION

Course Objective:
This course covers the theoretical computer science areas of formal languages and automata, computability and complexity. Topics covered include: regular and context-free languages; finite automata and pushdown automata; Turing machines; Church's thesis; computability - halting problem, solvable and unsolvable problems; space and time complexity; classes P, NP and PSPACE; NP-Completeness.
Learning Outcomes:
Upon successful completion, students will have the knowledge and skills to:
#At successful completion of the course, students should:
#Demonstrate advanced knowledge of formal computation and its relationship to languages
#Distinguish different computing languages and classify their respective types
#Recognise and comprehend formal reasoning about languages
#Show a competent understanding of the basic concepts of complexity theory

Responsible Moumita Akter
Last Update 03/01/2023
Completion Time 17 hours 31 minutes
Members 9
Intermediate 530225 Moumita Akter
    • language, alphabet, string vs word in automata theory
    • Theory of computation Bangla tutorial 59; NFA to DFA conversion example 1
    • Convert NFA to DFA with example| How to Convert NFA to DFA
    • Theory of computation Bangla tutorial, Formal definition of Regular Expression
    • Construction of Mealy Machine
    • Mealy and Moore State Machines (Part 1)
    • What is Context free grammar in TOC | Formal Definition
    • Chomsky Normal Form & CFG to CNF Conversion
    • What is Pushdown Automata in TOC | Definition & Explanation
    • Turing Machine - Introduction (Part 1)
    • Turing Machine for a^nb^n | Design Turing Machine
    • TOC(Set-1)
    • Minimization of DFA
    • CFG
    • Preview
    • NFA
    • Preview
    • Preview
    • Preview
  • Syllabus_TOC
    • Syllabus(TOC)
  • COURSE OUTLINE(TOC)
    • TOC_Outline
  • NU Question
    • Theory of Computation Questions (2017 - 2009)