Topic outline

  • General


    Welcome to Theory of Computation! This course is your gateway to understanding the fundamental principles that drive computation itself. We’ll explore topics like automata, formal languages, Turing machines, and computational complexity—key ideas that form the backbone of computer science.

    Get ready to challenge your thinking, dive deep into abstract concepts, and discover the power and limitations of what computers can solve. Whether you're curious about algorithms, logic, or the boundaries of computation, this class will sharpen your analytical skills and open your mind to new possibilities.
     Instructor's Details:
     Sadia Jannat Mitu
     Lecturer
     Department of Computer Science and Engineering
     Daffodil International University
     Contact Number: 01795582152
     Email: jannatmitu.cse@diu.edu.bd
     

    Course Rational:

    The Theory of Computing course aims to provide students with a deep understanding of fundamental principles in computer science. This course covers key topics such as automata theory, formal languages, computability, and complexity theory. Students will explore the theoretical underpinnings of computation, gaining insights into the limits and capabilities of algorithms and machines. The course equips students with essential knowledge for analyzing the efficiency and feasibility of algorithms, and lays the foundation for advanced studies in theoretical computer science.

    Course Objectives:

    1. To learn the basic concepts of Finite Automata.

    2. To understand different types of finite automata and their design approaches.

    3. To learn regular expressions and its conversion to Regular Language and finite automata.

    4. To learn context free grammar and its construction techniques.

    5. To learn Turing machine and its basics


    Course Learning Outcome:

    1.  Design deterministic finite automata with explaining the terms of Finite Automata

    2. Design non-deterministic Finite Automata along with the comparison of DFA and NFA.

    3. Apply conversion techniques of regular expression and Construct context free grammar by explaining derivation and parse tree and ambiguity.

    4. Illustrate Turing machines and its functionalities



    Course Content:

    • Introduction

    • Finite Automata

    • Deterministic Finite Automata (DFA)

    • Non-deterministic Finite Automata (NFA)

    • Conversion of NFA to DFA

    • Regular Expression

    • Pushdown Automata

    • Context free languages

    • Context free grammars

    • Turing Machines Basics                                                      

  • Lecture 1: Introduction

    COSC 545 - Theory of Computation (Spring 2012)

    Automata Theory is a branch of computer science that deals with designing abstract self propelled computing devices that follow a predetermined sequence of operations automatically. An automaton with a finite number of states is called a Finite Automaton. This is a brief and concise course that introduces the fundamental concepts of Finite Automata, Regular Languages, and Pushdown Automata before moving onto Turing machines and Decidability.

    Objectives of this lecture:

    • It comprises the fundamental mathematical properties of computer hardware, software and certain application .

    • The subject has obvious connections with engineering practice, and, as in many sciences.

    • Theory has proved its value to other parts of computer science. Many technologists and companies grew up out of the work of theorists. 

    • It deals with the definitions and properties of mathematical models of computation.

    Lecture Outcomes:

    At the end of the session students will be able to know about :

    • Computations basics

    • Automata Theory

    • Symbols and alphabet, Language

    • Sets, Function

    • Implication, Valid/invalid computation

    Lecture Contents:

    • Introduction

    • Automata Theory

    • Symbols and alphabet

    • Language

    • Sets

    • Function

    • Implication

    • Valid/invalid computation

  • Finite Automata (FA)

    Deterministic Finite Automaton - Tutorialspoint

    The term "Automata" is derived from the Greek word "αὐτόματα" which means "self-acting". An automaton (Automata in plural) is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically.

    An automaton with a finite number of states is called a Finite Automaton (FA) or Finite State Machine (FSM).


    Objective of this Lecture:

    1) To understand automata and its types

    2) To know about finite automata and it's real life example

    3) Relate automata theory to the real world computer science

    4) To know about categories of Finite automata

    5) To recognize any automata 

    6) To know DFA and NFA Computation

    Outcome:

    1) Automata and it's categories

    2) Formal Definitions

    3) Differentiate DFA and NFA

    4) String Acceptance in DFA and NFA  (String Acceptance)

    Content:

    1) Finite automata and it's categories

    2) DFA and NFA formal definition

    3) DFA and NFA computation 

  • Deterministic Finite Automata (DFA)

    Deterministic finite automaton - Wikipedia

    Learning objective:

    1) To know about DFA Construction

    Learning Outcome:

    1) Can construct DFA from any given regular language

    Content:

    1) Problem solving from DFA Construction


  • Non-deterministic Finite Automata (NFA)

    1.       Non deterministic Finite Automata definition

    2.       Formal Definition

    3.       String Acceptance

    4.       NFA Construction

  • NFA to DFA conversion

    1.       Why we need to convert NFA to DFA

    2.       How to convert NFA to DFA

    3.       Sub-set Construction Method

    4.       How to recognize any automata

    5.       How DFA and NFA works

    6.       Difference between dfa and nfa

    7.       How to draw a state diagram from a provided transition table

  • Midterm Syllabus

    1.   Introduction Session

    General discussion on the topic. Thought and experience sharing, Discuss course objectives, grading policies, etc. Concepts of Theory of computation.

    2.    Discussion about automata theory, how it works, Definitions and properties of deterministic finite automata (DFA), DFA computation, Basic DFA constructions.

    3.    DFA constructions, Different types of problem solving from DFA.

    4.    Methods of converting a non-deterministic finite automata to a deterministic finite automata

    5.    Process to draw an automata from transition table, how to differentiate a DFA from NFA, Why conversion is needed, discussion about real life application of finite automata.


  • Regular Expression

    1. Regular Language to Regular Expression

    2. Regular Expression to string generation

    3. Regular Expression to Finite Automata

    4. DFA to Regular Expression

  • Context Free Grammar (CFG)

    1. CFG Formal Definition

    2. Derivation

    3. Parse Tree

    4. Ambiguity

    5. CFG Construction

                  a) Regular Language

                   b) Context Free Language

  • Pushdown Automata (PDA)

    1. PDA Formal Definition

    2. PDA Construction

    3. Transition Function

    4. String acceptance

  • Turing Machine (TM)

    1. Turing Machine Basics

    2. How it works

    3. Turing Machine construction (Only for Regular Language)

    • Start with
    • End with
    • Does contain
    • Even Length
    • Odd Length

  • Quiz 1 Makeup

    • Presentation

      Design a finite automata for a real life scenario where it will focus to solve any real life issues which is not automated yet or can be added more automation.

      Note: You can take help from your text book (Chapter: Finite Automata) or any online resources. But remeber dirmatect copy paste from any source will effect your marks. 

      Reference Study:

      1. https://flaviocopes.com/finite-state-machines/

      2. https://www.cs.princeton.edu/courses/archive/spr06/cos116/FSM_Tutorial.pdf

      Example Idea:

      • a vending machine
      • a subway entrance turnstile
      • a heating system
      • an automated subway system
      • a self-driving car system
      • an elevator
      You may get idea from different resource to complete your task but direct copy paste will not be accepted. 

      Submission Guidelines:
      1. Make a presentation slide including the following details
      • Cover page with system title and your information (name, id. section, course code etc) 
      • Introduction (Summery description of your system)
      • Motivation (Why you choose this system, what makes it different from others)
      • Features of your system
      • System Description
      • System Design (NFA)
      • Relevant figures and others
      • Conclusion
      • Reference



      Watch the following video to know more details of presentation as well as final term exam topics.

      [For English Watch the following one]

      https://drive.google.com/open?id=1fpTPiju32f8k2IlBg9gCIh_B-LHePTtf&authuser=2

      [For Bengali Watch the following one]

      https://drive.google.com/open?id=1zIrM3s7l3o9ck2j6iYBYWF8HP95FQIeA&authuser=2


      • Quiz 3

        1. Read instructions provided in question carefully before starting the exam. 

        2. Submitted answer script must be in handwritten format and please write your Student ID in the top-right corner of every page of your answer script.

        3. Submitted answer script must be in pdf format with filename format (CourseCode-Section-StudentId. For example, SE234-O1-183-35-XXXXX-quiz3.pdf)


        • Quiz 3

          • Quiz 1

            • Quiz 3

              • Final Exam Syllabus


                • Topic 18

                  Quiz Type: Written 

                  Time: 25 min

                  • Write down your answers in a clean paper with your ID
                  • If you have multiple page write down your ID in the top of every page 
                  • You will get total 30 minutes. Within this time you have to complete your writing and all process for submission 
                  • No late submission will be allowed and don’t ask for extra time 
                  • Submit your answer within this time period (how much you can cover in 25 min, late submission will not be accepted)

                  • Survey Form