Chapter 8: Theory of Computation and Computer Graphics
Syllabus: AEiE08
Coverage: AEiE0801 through AEiE0806
Status: DRAFT - syllabus and assigned-question pass complete; independent source audit pending
Exam use: Recall, concept discrimination, automata hierarchy, graphics-transform recognition, and one-step matrix or clipping calculations
Chapter map
| Code |
Title |
Fast recognition cue |
AEiE0801 |
Finite automata |
Regular language, DFA/NFA, minimization, regex |
AEiE0802 |
Context free language |
CFG, parse tree, ambiguity, CNF, PDA |
AEiE0803 |
Turing machine |
Recognizer, decider, UTM, Church-Turing, limits |
AEiE0804 |
Computer graphics |
Raster vs vector, display hardware, I/O devices |
AEiE0805 |
Two-dimensional transformation |
Homogeneous matrix, viewing, 2D clipping |
AEiE0806 |
Three-dimensional transformation |
4x4 matrix, viewing pipeline, projection types |
Chapter rapid-revision sheet
| Topic |
Must-remember point |
| Regular language |
Exactly the languages accepted by DFA and NFA |
| DFA vs NFA |
Same expressive power; different transition style |
| Mealy vs Moore |
Output on transitions vs output on states |
| CFG |
One nonterminal on left side of each production |
| CFL vs PDA |
Exactly equivalent in expressive power |
| CNF |
Rules mainly of form \(A \to BC\) or \(A \to a\) |
| TM recognizer vs decider |
Recognizer may loop; decider must halt |
| Church-Turing thesis |
Thesis about effective computation, not a theorem |
| Raster vs vector |
Pixel grid vs drawn line segments |
| 2D transform |
Translation needs homogeneous coordinates |
| Composite order |
Rightmost matrix acts first for column vectors |
| Clipping |
Cohen-Sutherland uses outcodes; Liang-Barsky uses parameter bounds |
| 3D transform |
Use 4x4 matrices |
| Projection |
Orthographic and oblique are parallel; perspective shrinks with distance |
Assigned-question audit
| Target |
Deciding fact |
Result |
set1-043 |
Mealy output depends on present state and present input |
Supported by AEiE0801 |
set1-044 |
CFL is a proper subset of CSL, not the reverse |
Supported by AEiE0802 |
set1-045 |
a universal TM simulates an encoded TM on encoded input |
Supported by AEiE0803 |
set1-046 |
vector graphics use mathematically defined paths/primitives |
Supported by AEiE0804 |
set1-047 |
Liang-Barsky uses a parametric line and inequality bounds |
Supported by AEiE0805 |
set1-048 |
arbitrary-pivot 2D rotation applies inverse translation, rotation, then translation back |
Supported by AEiE0805 |
set1-089 |
every NFA has an equivalent DFA; both recognize exactly the regular languages |
Supported by AEiE0801 |
set1-090 |
Church-Turing says every effectively/algorithmically computable function is TM-computable |
Supported by AEiE0803 |
set1-091 |
Cohen-Sutherland uses region/outcodes |
Supported by AEiE0805 |
set1-092 |
a composite is the matrix product of multiple transformations |
Supported by AEiE0806 |
Sources and verification note
- Primary coverage authority:
syllab.md Chapter 8 (AEiE0801 to AEiE0806).
- Style and compression target:
notes/01-basic-electrical-electronics/ and notes/PLAN.md.
- Recommended theory verification: Sipser, Introduction to the Theory of Computation; Hopcroft, Motwani, and Ullman, Introduction to Automata Theory, Languages, and Computation.
- Recommended graphics verification: Hearn, Baker, and Carithers, Computer Graphics with OpenGL; ISO GKS/PHIGS and Khronos OpenGL specifications for named standards.
- These notes are review-oriented, not proof-oriented; if a future model paper uses nonstandard notation, check the underlying concept rather than memorizing the wording.
- No local model-paper option text is copied here; only the chapter coverage and likely recognition points are summarized.