Section outline

  • General

    Collapse all Expand all




                Instructor Name:      Aliza Ahmed Khan

                Designation:                Senior Lecturer

                 Email:                          aliza.cse@diu.edu.bd

                 Contact:                 01715918474

                 Office Address:           Room 805, AB04, Level -4,DSC.

                                       


    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

    • resource icon
      Lecture Content File
      Students must
      View
    • Students must
      Mark as done

      video :

    • assign icon
      Task 1 Assignment
      Opens: Monday, 16 February 2026, 12:00 AM
      Students must
      View
    • resource icon
      Lecture 2 File
      Students must
      Mark as done

  • 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 

    • url icon
      Reference Book Link URL
      Students must
      View

      Introduction to Theory of Computation

    • resource icon
      Lecture 2 File
      Students must
      View
    • resource icon
      Lecture 2.1 File
      Students must
      View
    • assign icon
      Assignment 1
      Opened: Wednesday, 21 August 2024, 3:00 PM
      Due: Wednesday, 21 August 2024, 3:45 PM
      Students must
      View
      Make a submission

      Submit your class assignment here

  • 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


    • resource icon
      DFA Construction Problems File
    • url icon
      Demonstration Lecture DFA Construction URL

          


    • assign icon
      DFA Construction Task 1 Section A Assignment
      Opened: Wednesday, 25 December 2024, 12:00 AM
      Due: Thursday, 26 December 2024, 12:00 AM
      Students must
      View
      Make a submission

      Construct DFA for the following language. Consider  Σ = {0,1} for every language. 

      •  {w | the length of w is exactly 5}
      • {w | the length of w is maximum 5}
      • {w | the length of w is minimum 5}
      • {w | w where |w| mod 4=0}
      • {w | w where |w| mod 4=1}
      • {w | w where |w| mod 4=2}
      • {w | w where |w| mod 4=3}

    • assign icon
      DFA Construction Task 1 Section B Assignment
      Opened: Saturday, 31 August 2024, 2:00 PM
      Due: Saturday, 31 August 2024, 5:30 PM

      Construct DFA for the following language. Consider  Σ = {0,1} for every language. 

      •  {w | the length of w is exactly 5}
      • {w | the length of w is maximum 5}
      • {w | the length of w is minimum 5}
      • {w | w where |w| mod 4=0}
      • {w | w where |w| mod 4=1}
      • {w | w where |w| mod 4=2}
      • {w | w where |w| mod 4=3}

    • url icon
      Demonstration Lecture DFA Construction Part 2 URL
    • lesson icon
      Practice Problems from DFA Constructions Lesson

      Chapter 1

      Page: 84

      Problem Number: 1.5, 1.6

    • assign icon
      Task 2 DFA Construction Section B Assignment
      Opened: Monday, 30 December 2024, 1:00 PM
      Due: Monday, 30 December 2024, 4:00 PM
      Students must
      View
      Make a submission

      1. {w|w where string starts with ba}

      2. {w|w where string does contains 0101 as substring}

      3. {w|w string start with b and ends with ab}

      4. {w| na(w) mod 4=2} 

      5. {w|w where every b should never followed by a}

    • url icon
      video lecture on DFA URL
      Students must
      Mark as done
    • assign icon
      Practice on DFA Assignment
      Opened: Tuesday, 17 September 2024, 12:00 AM
      Due: Tuesday, 24 September 2024, 12:00 AM
      Students must
      Mark as done

  • Non-deterministic Finite Automata (NFA)

    1.       Non deterministic Finite Automata definition

    2.       Formal Definition

    3.       String Acceptance

    4.       NFA Construction

    • resource icon
      NFA Construction File
    • url icon
      Lecture Video [Google Meet] URL
    • assign icon
      Task on NFA Construction Section A Assignment
      Opened: Saturday, 28 December 2024, 11:30 AM
      Due: Monday, 30 December 2024, 12:00 AM
      Students must
      View
      Make a submission

      Give state diagrams of NFAs with the specified number of states recognizing each of the following languages. In all parts, the alphabet is {0,1}.

      a. The language {w| w ends with 00}

      b. {w| w contains the substring 0101 (i.e., w = x0101y for some x and y)}

      c. {w| w begins with a 1 and ends with a 0}

      d. {w| w begins with substring 1101}

    • assign icon
      NFA exercise Assignment
      Opened: Sunday, 6 October 2024, 12:00 AM
      Due: Monday, 7 October 2024, 2:30 PM
      Students must
      Mark as done

      Submission deadline: 3rd October, 22

      Time: 2:30 PM

  • 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

    • resource icon
      NFA to DFA Conversion File
    • url icon
      Lecture Video [Google Meet] URL
    • assign icon
      Assessment on NFA to DFA Conversion Assignment
      Opened: Wednesday, 9 October 2024, 12:00 AM
      Due: Thursday, 10 October 2024, 12:00 AM
      Students must
      View
      Make a submission

      Convert the following NFA to DFA by using Subset construction Methd: 

      Consider {a,b} as input alphabet.

      1. String starts with ab

      2. String ends with ab

      3. String does contain ab

    • resource icon
      RE NFA DFA File
      Students must
      Mark as done

  • 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

    • resource icon
      Regular Expression File
    • resource icon
      Regular Expression Exercise File
    • assign icon
      Final Term Assignment Section: B
      Opens: Monday, 6 April 2026, 8:10 PM
      Due: Monday, 6 April 2026, 8:50 PM
    • assign icon
      Final Term Assignment Sction: A
      Opens: Wednesday, 8 April 2026, 1:02 PM
      Due: Wednesday, 8 April 2026, 1:52 PM
    • assign icon
      Final Term Assignment Sction: A (PC)
      Opens: Wednesday, 8 April 2026, 1:02 PM
      Due: Friday, 1 May 2026, 1:52 PM
    • resource icon
      Regular Expression Practice File
      Students must
      Mark as done
    • assign icon
      RE Exercise Assignment
      Opened: Wednesday, 20 November 2024, 3:00 PM
      Due: Wednesday, 20 November 2024, 4:30 PM
      Students must
      Mark as done

      Submit your class work here

    • assign icon
      DFA to RE Section C Assignment
      Opened: Monday, 7 April 2025, 12:00 AM
      Due: Monday, 7 April 2025, 12:00 AM
      Students must
      Mark as done

      Submit your class work here

      Deadline: 25/09/2023

      Time: 2:45 PM

    • assign icon
      RE to e-NFA Section D Assignment
      Opened: Monday, 7 April 2025, 12:00 AM
      Due: Monday, 7 April 2025, 12:00 AM
      Students must
      Mark as done

      Submit your class work here.

      Submission deadline: 25th September, 2023

    • assign icon
      Regular Expressions Section B Assignment
      Opened: Tuesday, 8 April 2025, 12:00 AM
      Due: Wednesday, 9 April 2025, 12:00 AM
      Students must
      Mark as done

      Find out e-NFA for the following expressions:

      1.  (0 + 10*)

      2.  (0*10*)

      3.  (0 + E) (1 +E) [E is epsilon]

      Convert the provided DFA from slide to RE. Follow the order 2,1,3

      Write down your id in top of every page.

      Submission deadline: Today’s class 

    • assign icon
      Regular Expressions Section A Assignment
      Opened: Wednesday, 9 April 2025, 12:00 AM
      Due: Thursday, 10 April 2025, 12:00 AM
      Students must
      Mark as done

      Submit your class work here 

    • assign icon
      DFA to RE Section E Assignment
      Opened: Sunday, 13 April 2025, 12:00 AM
      Due: Monday, 14 April 2025, 12:00 AM
      Students must
      Mark as done

      Submit your class work here.

    • forum icon
      Regular Expression Practice Forum
      Due: Friday, 27 September 2024, 1:30 AM
      Students must
      Mark as done

      Find out the "Regular Expression" for the following simple regular language where input alphabet is {0, 1} :

      a) {w| w where each string has even length}

      b) {w| w where each string has even length}

      c) {w| w where each string has length 3}


  • 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

  • Quiz 3

  • Quiz 1

  • Quiz 3

    • assign icon
      Presentation Assignment
      Opened: Tuesday, 10 December 2024, 12:00 AM
      Due: Tuesday, 17 December 2024, 12:00 AM
      Students must
      Mark as done

  • Final Exam Syllabus


  • Topic 17

    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























  • Topic 21

    • assign icon
      Quiz 4 Assignment
      Opened: Friday, 20 December 2024, 4:00 PM
      Due: Friday, 20 December 2024, 4:35 PM
      Students must
      Mark as done