Theory of Computation and Computer Graphics

1

Finite automata (FA) are abstract machines used to recognize regular languages; this topic also covers regular expressions and the pumping lemma, which is used to prove a language is NOT regular.

2

An FA is formally a 5-tuple (Q, Σ, δ, q0, F) — states, input alphabet, transition function, start state, and set of final/accepting states.

3

A DFA (Deterministic Finite Automaton) has exactly one transition for every state-symbol pair — the next state is always uniquely determined.

4

An NFA (Non-deterministic Finite Automaton) may have zero, one, or multiple transitions for a state-symbol pair, and may include ε-transitions (moves without consuming input) — unlike a DFA, the next state is not uniquely determined.

5

Equivalence of DFA and NFA: every NFA can be converted into an equivalent DFA via the subset construction method; both recognize exactly the class of regular languages.

6

Minimization of an FSM reduces a DFA to the smallest possible number of states by merging equivalent/indistinguishable states, while accepting exactly the same language.

7

A regular expression describes a regular language using the union (|), concatenation, and Kleene star (*) operators over an alphabet.

8

Equivalence of regular expressions and finite automata: every regular expression can be converted into an equivalent NFA (e.g., via Thompson's construction).

9

Conversely, every finite automaton can be converted into a regular expression — regex and FA have exactly the same expressive power.

10

The pumping lemma for regular languages is used to prove a language is NOT regular.

11

The pumping lemma states any sufficiently long string in a regular language can be split into three parts xyz, where the middle part y can be repeated ("pumped") any number of times and the resulting string still belongs to the language.

1

This topic covers context-free grammars (CFGs), parsing/derivation, grammar normal forms, pushdown automata (PDA), and closure properties of context-free languages.

2

A CFG is formally a 4-tuple (V, T, P, S): a set of variables (non-terminals), terminals, production rules, and a start symbol.

3

A derivation/parse tree graphically represents how a string is derived from the start symbol using the production rules.

4

A leftmost derivation always replaces the leftmost non-terminal first; a rightmost derivation always replaces the rightmost non-terminal first.

5

Top-down parsing builds the parse tree from the start symbol down towards the input string; bottom-up parsing starts from the input string and reduces up towards the start symbol.

6

The language of a grammar L(G) is the set of all terminal strings that can be derived from the start symbol.

7

A grammar is ambiguous if some string in its language has more than one distinct parse tree (or more than one leftmost derivation).

8

Chomsky Normal Form (CNF): every production is of the form A → BC or A → a (two variables, or a single terminal).

9

Greibach Normal Form (GNF): every production is of the form A → aα (a terminal followed by zero or more variables).

10

Backus-Naur Form (BNF) is a notation used to formally express context-free grammars, widely used to define the syntax of programming languages.

11

A Pushdown Automaton (PDA) is a finite automaton augmented with an auxiliary stack, giving it more memory/power than a plain finite automaton.

12

Equivalence of CFL and PDA: a language is context-free if and only if some PDA accepts it.

13

The pumping lemma for context-free languages is used to prove a language is NOT context-free.

14

Properties of context-free languages: CFLs are closed under union, concatenation, and Kleene star, but are NOT, in general, closed under intersection or complement.

1

The Turing Machine (TM) is the most powerful theoretical model of computation, forming the basis for the study of computability and computational complexity.

2

A TM consists of an infinite tape divided into cells, a read/write head that can move left or right, a finite set of states, and a transition function δ(q, X) = (q', Y, D) giving the new state, the symbol to write, and the direction (Left/Right) to move.

3

A string is accepted if the TM, starting in its initial state with the string on the tape, eventually reaches an accepting/final state.

4

As a language recognizer, a TM decides membership of strings in a language (accept/reject); as a computing function, a TM can compute a function's output by leaving the result written on its tape.

5

Multi-track TM: the tape is divided into several parallel tracks, letting each cell store multiple symbols at once.

6

Multi-tape TM: uses several independent tapes with independent heads — more convenient to program, but no more powerful (equivalent) than a single-tape TM.

7

Non-deterministic TM (NTM): may have multiple possible transitions for a given state-symbol pair; proven to be equivalent in power to a deterministic TM.

8

Universal Turing Machine (UTM): a single TM that can simulate any other TM, given an encoded description of that TM plus its input — the theoretical basis of the stored-program computer.

9

The Church-Turing Thesis states that any function that can be "effectively" (algorithmically) computed can be computed by some Turing Machine — it defines the intuitive limits of computability.

10

Computational complexity studies the amount of resources (time and space) a TM needs to solve a problem, usually expressed as a function of input size.

11

A problem is intractable if no algorithm can solve it in polynomial time (e.g., many NP-hard problems).

12

Reducibility transforms one problem into another to show that if one could be solved efficiently, so could the other — used to establish relative difficulty (e.g., NP-completeness proofs).

1

Computer graphics is the field concerned with the creation, manipulation, and storage of images/pictures using a computer.

2

Raster-scan display: the image is composed of a grid of pixels stored in a frame buffer and refreshed line-by-line (row by row); the dominant technology in modern monitors.

3

Vector (random-scan) display: draws an image as a series of straight lines directly from one endpoint to another (not pixel-based); used in early graphics terminals and oscilloscope-style displays.

4

A display processor (graphics controller) offloads image-generation tasks from the main CPU, managing the frame buffer and screen refresh independently.

5

Output devices include the monitor (CRT/LCD), plotter, and printer.

6

Input devices include the keyboard, mouse, digitizer/graphics tablet, scanner, light pen, and joystick.

7

General programming packages (e.g., OpenGL) provide graphics primitives/functions that a programmer uses to build custom applications.

8

Special-purpose application packages (e.g., CAD software, image editors) are ready-made tools for specific tasks.

9

Graphics software standards ensure portability of graphics programs across different hardware.

10

GKS (Graphical Kernel System), PHIGS (Programmer's Hierarchical Interactive Graphics System), and OpenGL are widely referenced standard graphics APIs.

1

This topic covers the basic geometric transformations used to manipulate 2D objects, how they combine, and how a scene is mapped from world coordinates to the screen.

2

Translation moves an object by a displacement (tx, ty) without changing its shape or orientation.

3

Rotation rotates an object by an angle θ about a reference point (commonly the origin).

4

Scaling changes the object's size by scale factors (sx, sy) along the x and y axes.

5

Reflection produces a mirror image of the object about a specified axis or line.

6

Shear slants/distorts the shape of an object along the x-axis or y-axis.

7

Homogeneous coordinates represent 2D points with an extra coordinate (x, y, 1), allowing all transformations (including translation) to be expressed as 3×3 matrix multiplications.

8

A composite transformation combines multiple transformations (e.g., translate then rotate then scale) into a single matrix by multiplying the individual transformation matrices — more efficient than applying each transformation separately.

9

The 2D viewing pipeline maps a scene from world coordinates to viewing coordinates, then to normalized coordinates, and finally to device/screen coordinates.

10

A window defines the area of interest in world coordinates; a viewport defines where that window is displayed on the screen — the window-to-viewport transformation maps one onto the other.

11

Clipping removes the parts of a picture that lie outside the defined window/viewing area before display.

12

Cohen-Sutherland clipping assigns each line endpoint a 4-bit region code based on its position relative to the clip window (9 regions); lines are then quickly accepted, rejected, or clipped using these codes.

13

Liang-Barsky clipping uses the parametric equation of a line and solves a set of inequalities to find the visible portion — generally more computationally efficient than Cohen-Sutherland.

1

This topic extends 2D transformations into three dimensions and introduces the 3D viewing pipeline along with projection methods used to display 3D scenes on a 2D screen.

2

3D translation, rotation, scaling, reflection, and shear extend their 2D counterparts into three dimensions, using 4×4 homogeneous transformation matrices operating on (x, y, z, 1) coordinates.

3

3D rotation can be performed about the x-axis, y-axis, or z-axis, each with its own rotation matrix.

4

3D composite transformation: multiple 3D transformations are combined into a single 4×4 matrix by multiplying the individual matrices together — same principle as 2D composite transformation.

5

The 3D viewing pipeline begins with modeling transformation, which places individual objects into the overall world scene.

6

Next is the viewing transformation, which transforms the scene into the camera/viewer's coordinate system.

7

This is followed by the projection transformation, which maps the 3D scene onto a 2D viewing plane, and finally the viewport transformation, which maps to screen coordinates.

8

Parallel projection: projectors (projection lines) are parallel to each other; preserves relative proportions/dimensions of the object, useful for engineering/technical drawing.

9

Orthographic projection is a type of parallel projection where the projectors are perpendicular to the view plane, producing standard views (e.g., top, front, side).

10

Oblique projection is a parallel projection where projectors are NOT perpendicular to the view plane.

11

Perspective projection: projectors converge to a single point (the center of projection), so objects farther from the viewer appear smaller — gives a realistic sense of depth, used in visual rendering and games.