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)

Previousset-6Next6.1 Introduction to Finite Automata

Last updated