Topic outline

• Select topic General

  General

  Collapse all Expand all

  Lecturer : Dr. Mohd Soperi bin Mohd Zahid Semester : Semester x 201x/xx
  Synopsis: This course introduces students to a formal language and automata theory. It will emphasize on grammar, language and abstract machine such as context Free Grammar, Finite Automata, Push Down Automata, and Turing Machine. The course will also provide practice on the acceptability of data by these machines. At the end of the course, students should be able to apply the theory in constructing this abstract machine and testing them with the right data.
  This work, SCJ3203 Theory of Computer Sciences by MOHD SOPERI BIN MOHD ZAHID, SAZALI ABDUL MANAF, and PARIDAH SAMSURI is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
• Select topic Topic 1

  Topic 1
  Introduction to Theory of Computer Science
  This topic provides general introduction of the course and a review of related mathematical background and notations that are required to understand the materials in the course.
  

  • Overview of Automata, Complexity and Computability Theories
  • Mathematical Preliminaries
    

  • Select activity Lecture Slides (pdf)

    

    Lecture Slides (pdf) File
• Select topic Topic 2

  Topic 2
  Strings and Languages
  Problems in modeling of computation are described in terms of strings and languages. This topics provides an introduction to strings and languages and the relationship between them.
  

  • String and its operations
  • Language Specification

  • Select activity Lecture Slides (pdf)

    

    Lecture Slides (pdf) File
• Select topic Topic 3

  Topic 3
  Finite Automata
  This topic describes the simplest models of computation and the problems that they can solve which are represented as regular languages.
  

  • Deterministic Finite Automata (DFA)
  • Non-deterministic Finite Automata (NFA)
  • Regular Languages
    

  • Select activity Lecture Slides (pdf)

    

    Lecture Slides (pdf) File
• Select topic Topic 4

  Topic 4
  Context-Free Languages (CFL)
  Context-free languages represent a set of problems that cannot be solved by finite automaton but can be solved by another model of computation called Push-down automata (PDA). This topic describes how to write grammars of CFG and converting the grammars into normal forms.
  

  • Context-free Grammar (CFG)
  • Chomsky and Grebaich Normal Forms
  • Push-down Automata (PDA)
    

  • Select activity Lecture Slides (pdf)

    

    Lecture Slides (pdf) File
• Select topic Topic 5

  Topic 5
  Turing Machines (TM)
  This topic describes Turing Machines as model of computation for a general purpose computer. In addition, it also provides the technique to decide whether a problem is solvable by a computer (decidable) or not (undecidable).
  

  • TM Computation
  • Algorithm
  • Decidable vs Undecidable Problems
    

  • Select activity Lecture Slides (pdf)

    

    Lecture Slides (pdf) File