6. Theory of Computation and Computer Graphics (ACtE06)

6.1 Introduction to Finite Automata (ACtE0601)

Finite Automata (FA)

• Definition: A mathematical model of computation used to recognize patterns.
• Components:
  • States ($Q$): Finite set of states.
  • Alphabet ($\Sigma$): Set of input symbols.
  • Transition Function ($\delta$): Defines state changes.
  • Start State ($q_0$): Initial state.
  • Final State ($F$): Accepting states.

Types of Finite Automata

• Deterministic Finite Automata (DFA):
  • One possible transition per input symbol.
  • Defined as: $$DFA = (Q, \Sigma, \delta, q_0, F)$$
• Non-Deterministic Finite Automata (NDFA):
  • Multiple transitions per input symbol.
  • Uses epsilon ($\epsilon$) transitions (moves without input).
  • Can be converted to DFA.

Regular Expressions and Finite Automata

• Regular Expressions: Notations for defining regular languages.
• Equivalence of Regular Expressions and Finite Automata: Every regular expression has an equivalent FA.

Pumping Lemma for Regular Languages

• Used to prove that a language is not regular.
• Statement:
  If $L$ is a regular language, there exists a constant $p$ such that any string $s$ in $L$ with $|s| \geq p$ can be split into: $$s = xyz$$ where:
  • $|xy| \leq p$,
  • $|y| > 0$,
  • $xy^n z$ is in $L$ for all $n \geq 0$.

6.2 Introduction to Context-Free Language (ACtE0602)

Context-Free Grammar (CFG)

• Definition: A set of recursive rewriting rules used to generate patterns of strings.
• Notation: $$G = (V, \Sigma, P, S)$$ where:
  • $V$ = Set of non-terminal symbols.
  • $\Sigma$ = Set of terminal symbols.
  • $P$ = Set of production rules.
  • $S$ = Start symbol.

Parse Tree & Ambiguous Grammar

• Parse Tree: Visual representation of the structure of a string based on CFG.
• Ambiguous Grammar: A grammar is ambiguous if a string has multiple parse trees.

Normal Forms of CFG

• Chomsky Normal Form (CNF):
  • Each production is of the form: $$A \rightarrow BC \quad \text{or} \quad A \rightarrow a$$
• Greibach Normal Form (GNF):
  • Each production is of the form: $$A \rightarrow a\alpha$$ where $a$ is a terminal and $\alpha$ is a sequence of non-terminals.

Pushdown Automata (PDA)

• Automaton that recognizes context-free languages.
• Has a stack for memory.

Pumping Lemma for Context-Free Languages

• Used to prove a language is not context-free.

6.3 Turing Machine (ACtE0603)

Definition and Notation

• Turing Machine (TM): A more powerful model of computation than FA and PDA.
• Notation: $$TM = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$$ where:
  • $\Gamma$ = Tape alphabet.
  • $\delta$ = Transition function.

Types of Turing Machines

• Multi-Tape Turing Machine: Uses multiple tapes.
• Non-Deterministic Turing Machine (NDTM): Can transition to multiple states.
• Universal Turing Machine: Simulates any other Turing machine.

Church-Turing Thesis

• States that any computation performed by a mechanical process can be done by a Turing Machine.

Computational Complexity

• Time Complexity: Measures running time based on input size.
• Space Complexity: Measures memory usage.
• Intractability: Problems that cannot be solved efficiently.

6.4 Introduction to Computer Graphics (ACtE0604)

Overview of Computer Graphics

• Definition: The creation, manipulation, and representation of visual images using a computer.
• Applications: Gaming, UI design, Animation.

Graphics Hardware

• Display Technology: CRT, LCD, LED, OLED.
• Raster-Scan Display: Uses pixels (bitmap).
• Vector Display: Uses mathematical equations.
• Output Devices: Monitors, Printers.
• Input Devices: Mouse, Graphics Tablet.

Graphics Software

• Software Standards: OpenGL, DirectX.

6.5 Two-Dimensional (2D) Transformations (ACtE0605)

Basic 2D Transformations

• Translation: Moves objects in space. $$\begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} x + T_x \\ y + T_y \end{bmatrix}$$
• Rotation: Rotates around an origin. $$\begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix}$$
• Scaling: Changes the size of objects. $$\begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} S_x \times x \\ S_y \times y \end{bmatrix}$$
• Reflection & Shear: Used for mirroring and skewing.

2D Viewing Pipeline & Clipping

• Cohen-Sutherland Line Clipping: Determines which lines are inside the viewing window.
• Liang-Barsky Clipping: More efficient than Cohen-Sutherland.

6.6 Three-Dimensional (3D) Transformations (ACtE0606)

Basic 3D Transformations

• Translation, Rotation, Scaling, Reflection, Shearing (similar to 2D).

3D Viewing Pipeline

• Process:
  • Modeling Transformation: Defines the object’s shape.
  • Viewing Transformation: Defines the camera’s position.
  • Projection Transformation: Converts 3D objects into 2D images.

Projection Types

• Orthographic Projection: Parallel projection (used in engineering drawings).
• Perspective Projection: Objects appear smaller as they move farther.