Skip to Content
Live class going on, get early discount!
LicenseComputer6. Theory-of-computation-and-computer-graphicsREADME

6. Theory of Computation and Computer Graphics

6.1 Introduction to Finite Automata

  • Introduction to Finite Automata and Finite State Machines
  • Equivalence of DFA and NDFA
  • Minimization of Finite State Machines
  • Regular Expressions
  • Equivalence of Regular Expression and Finite Automata
  • Pumping Lemma for Regular Language

6.2 Introduction to Context-Free Language

  • Introduction to Context-Free Grammar (CFG)
  • Derivative Trees (Bottom-up and Top-down Approach, Leftmost and Rightmost Derivation)
  • Language of a Grammar
  • Parse Tree and its Construction
  • Ambiguous Grammar
  • Chomsky Normal Form (CNF), Greibach Normal Form (GNF), Backus-Naur Form (BNF)
  • Push Down Automata
  • Equivalence of Context-Free Language and PDA
  • Pumping Lemma for Context-Free Language
  • Properties of Context-Free Language

6.3 Turing Machine

  • Introduction to Turing Machines (TM)
  • Notations of Turing Machine
  • Acceptance of a String by a Turing Machine
  • Turing Machine as a Language Recognizer
  • Turing Machine as a Computing Function
  • Turing Machine as an Enumerator of Strings of a Language
  • Turing Machine with Multiple Tracks
  • Turing Machine with Multiple Tapes
  • Non-Deterministic Turing Machines
  • Church-Turing Thesis
  • Universal Turing Machine for Encoding of Turing Machines
  • Computational Complexity, Time and Space Complexity of a Turing Machine
  • Intractability, Reducibility

6.4 Introduction to Computer Graphics

  • Overview of Computer Graphics
  • Graphics Hardware (Display Technology, Architecture of Raster-Scan Displays, Vector Displays, Display Processors, Output and Input Devices)
  • Graphics Software and Software Standards

6.5 Two-Dimensional Transformation

  • Two-Dimensional Translation, Rotation, Scaling, Reflection, Shear Transformation
  • 2D Composite Transformation
  • 2D Viewing Pipeline
  • World to Screen Viewing Transformation and Clipping (Cohen-Sutherland Line Clipping, Liang-Barsky Line Clipping)

6.6 Three-Dimensional Transformation

  • Three-Dimensional Translation, Rotation, Scaling, Reflection, Shear Transformation
  • 3D Composite Transformation
  • 3D Viewing Pipeline
  • Projection Concepts (Orthographic, Parallel, Perspective Projection)
Last updated on
set-26.1-introduction-to-finite-automata