Theory of Computation and Computer Graphics

Answer: B. Pumping lemma

Pumping lemma is the technique to determine if a language is regular or non-regular.

Answer: B. Pumping lemma

Pumping lemma proves language is non-regular by contradiction.

Answer: D. Memory unit

FSM has input/output alphabet, states, transitions. Memory unit is not standard component.

Answer: A. A DFA has exactly one transition for each symbol from every state, while an NFA may have zero, one, or many transitions (including ε-moves) for the same symbol from a state.

Both DFA and NFA are models of computation for regular languages, but their transition behavior differs. In a DFA, the transition function is: δ : Q × Σ → Q For each state q ∈ Q and each symbol a ∈ Σ, there is exactly one defined next state δ(q, a). This means the automaton's behavior is completely determined by the current state and current input symbol. There is no ambiguity: at any step, only one path is possible. This is why the machine is ‘deterministic’. In an NFA, the transition function is: δ : Q × Σ_ε → P(Q) where Σ_ε = Σ ∪ {ε} and P(Q) is the power set of Q. For a given state and input symbol, δ may return: • zero states (no transition), • one state, or • multiple possible next states. Additionally, NFAs may have ε-transitions that consume no input symbol but move the machine to new states. Because of this, an NFA can be in a *set* of possible current states at any point in a conceptual execution. Despite this difference, DFAs and NFAs are equivalent in expressive power: for every NFA there exists an equivalent DFA recognizing the same language. The usual construction is the subset construction, where each DFA state represents a subset of NFA states. However, the DFA can have up to 2^|Q_NFA| states in the worst case. So the essential difference is not in the class of languages recognized, but in the form of the transition function and the degree of nondeterminism allowed during computation.

Answer: B. Because for every NFA there exists a DFA that recognizes the same language, constructed by subset construction.

DFA and NFA are equivalent in *language recognition power* for regular languages. This means any language recognized by some NFA can also be recognized by some DFA, and every DFA trivially is an NFA (with restricted transitions). The central construction is the *subset construction* (also called powerset construction): • Given an NFA N = (Q, Σ, δ, q₀, F), construct a DFA D = (Q', Σ, δ', q₀', F') such that L(D) = L(N). • Each state in Q' is a subset of Q (so Q' ⊆ P(Q)). Intuitively, a DFA state encodes all possible NFA states that the NFA could be in after reading some prefix of the input. • The start state q₀' of the DFA is the ε-closure of {q₀} (all states reachable from q₀ via ε-moves). • For each DFA state S ⊆ Q and symbol a ∈ Σ, define: δ'(S, a) = ε-closure(⋃_{q∈S} δ(q, a)) • A DFA subset S is accepting if S intersects F: S ∩ F ≠ ∅. This construction systematically removes nondeterminism by letting the DFA compactly track all possible NFA states at once. While the resulting DFA can, in the worst case, have up to 2^|Q| states, it always exists and recognizes the same language. Because of this theorem, NFAs are often used as a convenient design tool (they are easier to construct from regular expressions), and then converted into DFAs for implementation in lexical analyzers, pattern matchers, and hardware finite state machines.

Answer: B. To merge equivalent states so that the DFA has the minimum number of states recognizing the same language.

DFA minimization is the process of transforming a given DFA into an equivalent DFA (recognizing the same language) that has the minimum possible number of states. Two states are *equivalent* if, for every possible input string w, either both states accept w (from that state onward) or both reject w. Intuitively, the future behavior of the automaton from those states is indistinguishable. Main idea: • Partition the set of states into equivalence classes under the Myhill–Nerode equivalence relation. • Each equivalence class is collapsed into a single state in the minimized DFA. • Transitions between equivalence classes are defined naturally from transitions of representative states. Common algorithmic view: 1. Initially partition states into accepting and non-accepting sets (they are obviously distinguishable if one is accepting and the other is not). 2. Iteratively refine partitions: for any block of states, split it if some states in the block transition into different blocks under some input symbol. 3. Continue until no more refinement occurs. Each resulting block represents one state of the minimal DFA. Importance: • Reduced memory/storage: fewer states mean smaller transition tables or hardware. • Faster execution: fewer states and transitions to process. • Conceptual clarity: the minimal DFA reveals the intrinsic complexity of the language (number of distinct Myhill–Nerode equivalence classes). • In compiler construction, minimal DFAs make lexical analyzers more efficient. Uniqueness: Apart from renaming of states, the minimal DFA for a given regular language is unique. This property is useful when comparing regular languages or reasoning about their complexity.

Answer: B. Regular expressions and finite automata (DFA/NFA) describe exactly the same class of languages: the regular languages.

Kleene's Theorem is the central result connecting regular expressions and finite automata. It states that the following three formalisms are equivalent in expressive power: 1. Deterministic finite automata (DFA), 2. Nondeterministic finite automata (NFA), and 3. Regular expressions. All three describe exactly the class of *regular languages*. Direction 1: RE → NFA/DFA. • Given a regular expression, you can systematically construct an NFA using Thompson's construction. For basic symbols, concatenation, alternation (|), and Kleene star (*), there are standard NFA fragments that can be combined. • Then, using subset construction, the NFA can be turned into an equivalent DFA. Direction 2: DFA/NFA → RE. • Given a finite automaton, there are state-elimination algorithms that remove states one by one and accumulate edge labels as regular expressions. The final result is a regular expression denoting the same language. Therefore, regular expressions, DFA, and NFA are different syntactic or structural views of the same underlying thing: regular languages. Regular expressions are more compact and convenient to write and reason about patterns, while automata are more suitable for mechanical implementation (e.g., lexical analyzers or hardware circuits).

Answer: A. That every long enough string in a regular language can be decomposed into xyz where some middle part y can be repeated any number of times and the resulting strings all remain in the language.

The pumping lemma for regular languages is a *necessary condition* for a language to be regular. It does not characterize regular languages completely, but it is an extremely useful tool for proving that certain languages are *not* regular. Statement (informal): If L is a regular language, then there exists a constant p (the pumping length) such that any string w ∈ L with |w| ≥ p can be split into three parts w = xyz satisfying: 1. |y| > 0 (the pumped part is non-empty), 2. |xy| ≤ p (the initial segment xy lies within the first p symbols), 3. For all i ≥ 0, the string x y^i z ∈ L. Intuition: • Because L is regular, there exists a DFA with a finite number of states, say p states. • Any string of length at least p causes the DFA, as it reads the first p symbols, to visit at least one state twice (Pigeonhole Principle). • The part of the input that causes this loop corresponds to y. Since the automaton can loop that segment any number of times and remain in an accepting path, the pumped strings x y^i z must all be in L. How it is used: • To show a language L is *not* regular, you assume it *is* regular and thus must satisfy the pumping lemma. • You choose a string w in L of length ≥ p, then argue that for *every* way to split w into xyz obeying conditions 1 and 2, there exists some i (often i = 0 or 2) such that x y^i z ∉ L. • This contradicts the pumping lemma, hence L cannot be regular. Example: L = { a^n b^n | n ≥ 0 }. • Intuitively not regular; counting equal numbers of a's and b's requires memory beyond a finite automaton. • Suppose L is regular. Let p be pumping length. Consider w = a^p b^p. • By conditions, y consists only of a's within first p positions. Pumping y (e.g. i = 0) changes number of a's but not b's, giving a^{p - |y|} b^p, which is not in L. • Contradiction ⇒ L is not regular. Thus, the pumping lemma is a powerful *negative tool*: if a language fails the pumping lemma, it is definitely not regular. If it satisfies the lemma, it might still be non-regular (the lemma is not a sufficient condition).

Answer: B. It cannot remember arbitrarily large amount of information

The basic limitation of finite state machines is that they cannot remember arbitrarily large amounts of information. FSM has: (1) Fixed, finite number of states - Defined at design time, (2) Limited memory - Only the current state is remembered, (3) No stack or unbounded storage - Cannot push/pop arbitrary amounts of data. This fundamental limitation means FSMs: (1) Cannot parse context-free languages (like balanced parentheses), (2) Cannot count unbounded repetitions, (3) Cannot match arbitrarily nested structures. Examples of what FSMs cannot do: (1) Recognize anbn (equal number of a's followed by b's), (2) Match nested parentheses, (3) Parse programming language expressions with nesting. Formal language theory: (1) Regular languages - Recognized by FSMs, (2) Context-free languages - Require push-down automata (add stack), (3) Recursively enumerable languages - Require Turing machines. To overcome this, we use: (1) Push-down automata (add one stack), (2) Turing machines (add unlimited tape), (3) Practical alternatives - Compiler theory, parsing techniques. This limitation is why real parsing requires more powerful machines than FSMs. Application implications: (1) Network protocols - Can use FSMs, (2) Programming language compilation - Need more powerful machines, (3) Lexical analysis - FSMs sufficient, (4) Syntax analysis - Need push-down automata or more.

Answer: B. b) Start state

In an FSM (Finite State Machine), the initial state is also called the Start state. This is the state where the FSM begins its operation before processing any inputs. Every FSM has exactly one initial state (unless specified otherwise). Final or accepting states are different from the initial state. The FSM transitions from the start state based on inputs and defined transition rules.

Answer: C. Pushdown Automaton (PDA)

Answer: A. True

Answer: B. Prove a language is not regular

Answer: B. Any string of a's and b's

Answer: B. All strings with equal number of a's and b's

Answer: B. Reduce the number of states without changing the language

Answer: C. NFAs and DFAs have equivalent computational power

Answer: B. 3

Answer: D. None, DFAs and regular expressions are equivalent

Answer: B. Output depends only on current state

Answer: A. Output depends only on current state

Answer: C. Type 2

PDAs recognize Type 2 (context-free) grammars and languages.

Answer: B. A hierarchical structural derivation of how a start symbol generates a string in the language using production rules.

A parse tree (also called derivation tree) in the context of a context-free grammar (CFG) visually represents how a string in the language is derived from the start symbol using the grammar's productions. Given a CFG G = (V, Σ, R, S): • V: set of non-terminals, • Σ: set of terminals, • R: set of production rules of the form A → α, • S: start symbol. A parse tree has the following properties: • The root of the tree is labeled with the start symbol S. • Each interior node is labeled with a non-terminal A ∈ V. • Each leaf node is labeled with a terminal symbol ∈ Σ or with ε. • For each interior node labeled A, with children labeled α₁, α₂, …, α_k (in order), there is a production rule A → α₁α₂…α_k in R. The *yield* of a parse tree is the string obtained by reading off the leaf nodes from left to right, ignoring ε leaves. This yield is a string in the language generated by the grammar. Parse trees encode the *syntactic structure* of a string according to a grammar. The tree reveals hierarchy, such as which substrings group together as subexpressions, phrases, or statements. This is essential in compilers, where syntax trees are used as intermediate representations for semantic analysis and code generation. Different derivations (leftmost vs rightmost) of the same string can lead to the same parse tree, but an *ambiguous grammar* allows at least one string with *two distinct parse trees*. So parse trees are also central for discussing ambiguity in context-free grammars.

Answer: B. A grammar for which at least one string in the language has more than one distinct parse tree.

A context-free grammar G is called *ambiguous* if there exists at least one string w in L(G) that has two or more distinct parse trees (equivalently, two distinct leftmost or rightmost derivations). Ambiguity is about *syntactic structure*, not just membership. The same string w can be derived in two structurally different ways, leading to different parse trees. This means the grammar does not specify a unique structure for that string, which is problematic for many applications (e.g., programming languages, where meaning depends on structure). Example: Classic arithmetic expression grammar: E → E + E | E * E | (E) | id The expression "id + id * id" can be parsed as: 1. (id + id) * id (if + has higher precedence) 2. id + (id * id) (if * has higher precedence) Both are allowed by this grammar, and hence the grammar is ambiguous. To remove ambiguity, we refine the grammar by encoding operator precedence and associativity: E → E + T | T T → T * F | F F → (E) | id This new grammar ensures that * has higher precedence than +, and parse trees become unique for arithmetic expressions under these rules. Some context-free languages are *inherently ambiguous*, meaning that *every* grammar generating that language is ambiguous. For such languages, it is impossible to design an unambiguous grammar. In compiler design, unambiguous grammars (or controlled ambiguity resolved by precedence rules in the parser) are essential, since compilers need a unique parse for each source program.

Answer: B. To restrict productions to either A → BC or A → a, which simplifies theoretical proofs (like CYK parsing algorithm) and analysis.

Chomsky Normal Form (CNF) is a restricted form of CFG in which every production is of one of the following forms: 1. A → BC (two non-terminals on the right-hand side), 2. A → a (a single terminal), 3. S → ε (only allowed if the language includes the empty string and S does not appear on the right-hand side of any rule). The main purposes for converting to CNF are: • To simplify theoretical analysis of context-free languages. • To support algorithms like the CYK (Cocke–Younger–Kasami) parsing algorithm, which assumes CNF. • To show closure properties and decidability results more easily. Transformation steps (overview): 1. Eliminate null (ε) productions, except possibly S → ε. 2. Eliminate unit productions (A → B). 3. Eliminate useless symbols (non-terminals that cannot derive any terminal string or are not reachable from S). 4. Convert remaining long right-hand sides into binary form using new non-terminals. 5. Ensure right-hand sides with a mixture of terminals and non-terminals are adjusted so that terminals appear alone (introduce new non-terminals for terminals if needed). Important points: • Language preserved: The new grammar generates the same language (possibly adjusting for ε). • CNF does *not* guarantee unambiguity. An ambiguous grammar can be converted to a different ambiguous grammar in CNF. • CNF is not for practical parser implementation (parsers often use other forms), but it is very useful in proofs (e.g., proving that every context-free language has a polynomial-time membership algorithm). Thus, CNF is a canonical restricted form that simplifies reasoning about context-free grammars and supports theoretically clean parsing algorithms.

Answer: B. A finite automaton equipped with a stack, used to recognize exactly the class of context-free languages.

A Pushdown Automaton (PDA) extends finite automata with an additional *stack* memory. Formally, a PDA is a 7-tuple: M = (Q, Σ, Γ, δ, q₀, Z₀, F) where: • Q is the finite set of states, • Σ is input alphabet, • Γ is stack alphabet, • δ is transition function (Q × Σ_ε × Γ → P(Q × Γ*)), • q₀ is start state, • Z₀ is initial stack symbol, • F is set of accepting states. The stack allows the PDA to store unbounded information (in a last-in, first-out manner), enabling it to handle nested and balanced structures that finite automata cannot. Relationship to CFLs: • Every context-free language (CFL) can be recognized by some PDA (often built from a CFG via standard constructions). • Conversely, for every PDA there exists a CFG that generates exactly the same language. • Therefore, PDAs and CFGs are equivalent in expressive power: both characterize context-free languages. Intuition: • Regular languages are not powerful enough to handle patterns that require counting or nested dependencies (e.g., a^n b^n, balanced parentheses). A finite automaton has only finitely many states and hence limited memory. • PDA's stack allows it to remember an unbounded number of symbols (e.g., count of 'a's) as long as the computation is well-structured. Example: Language L = { a^n b^n | n ≥ 0 }. • PDA can push a symbol onto the stack for each a read, then pop one symbol for each b read. If stack is empty exactly when input ends, accept. Acceptance conditions for PDA: • Acceptance by final state: reach an accepting state after consuming entire input (stack may be non-empty or empty depending on design). • Acceptance by empty stack: consume input and empty the stack (final state not necessarily required). Thus, PDA is the machine model corresponding to context-free grammars, just as finite automata correspond to regular expressions.

Answer: B. It gives a decomposition w = uvxyz with two pumpable parts v and y, instead of one (y) as in the regular pumping lemma.

The pumping lemma for context-free languages (CFLs) is a necessary condition for a language to be context-free, analogous in spirit to the pumping lemma for regular languages, but with a more complex decomposition. Formal (informal) statement: If L is an infinite context-free language, then there exists a constant p (pumping length) such that any string w in L with |w| ≥ p can be written as w = u v x y z satisfying: 1. |v y| > 0 (at least one of v or y is non-empty), 2. |v x y| ≤ p (the 'middle' portion has bounded length), 3. For all i ≥ 0, the string u v^i x y^i z ∈ L. Key differences from regular pumping lemma: • Regular lemma decomposes w into xyz with only one repeated segment y. • CFL lemma decomposes w into uvxyz with two pumpable substrings v and y, which are pumped *in parallel* (both repeated i times). • The decomposition is based on repeated non-terminals in a sufficiently deep parse tree derived from the pumping length. Usage: • Like the regular pumping lemma, it is primarily a *negative* tool: to prove that a language is *not* context-free by showing it fails the lemma. • Typical strategy: assume L is context-free, let p be pumping length, choose a particular w ∈ L with |w| ≥ p, consider all possible decompositions into uvxyz satisfying the conditions, and show there exists some i (often 0 or 2) such that u v^i x y^i z ∉ L. Example: L = { a^n b^n c^n | n ≥ 0 }. • Intuitively non context-free (requires two equalities: number of a's = b's and b's = c's). • Use pumping lemma for CFL to show any uvxyz decomposition cannot preserve both equalities for all i. Important: As with the regular pumping lemma, the CFL pumping lemma is necessary but not sufficient. Some non-context-free languages may still satisfy the lemma, but no context-free language can violate it. Also, it is strictly weaker than other characterizations like Ogden’s lemma, which is often more convenient for non-CFL proofs.

Answer: B. Push down automata

Push-down automata (PDA) is the specific machine for context-free grammars (CFG). PDA characteristics: (1) Adds a stack to FSM - Can store and retrieve unlimited information (within bounds of problem), (2) Recognizes context-free languages, (3) Useful for parsing programming languages. Automata hierarchy and languages: (1) FSM - Recognizes Regular languages, no memory, (2) PDA - Recognizes Context-free languages, has stack, (3) Linear Bounded Automata - Recognizes Context-sensitive languages, limited tape, (4) Turing Machine - Recognizes Recursively enumerable languages, unlimited tape. Why PDA for CFG: (1) Stack allows matching nested structures (parentheses, brackets), (2) Can parse recursive grammars, (3) Can recognize patterns like anbn (equal a's then b's), (4) Directly corresponds to grammar derivation. Practical applications: (1) Compiler parsing - Use PDA for syntax analysis, (2) Expression evaluation - Parentheses matching, (3) Programming language design - CFG describes language syntax. PDA implementation: (1) Scan input, (2) Push/pop from stack based on input and current state, (3) Accept if input consumed and stack in correct state. Formal definition: PDA = (Q, Σ, Γ, δ, q0, Z0, F) where Q = states, Σ = input alphabet, Γ = stack alphabet, δ = transition function, q0 = initial state, Z0 = initial stack symbol, F = final states.

Answer: C. c) Empty string

In CFG (Context-Free Grammar), ε (epsilon) represents the empty string. It denotes zero-length string or no input. ε production allows a non-terminal to derive nothing, enabling optional grammar elements. For example: A → ε means non-terminal A can produce an empty string. This is useful for making parts of grammar optional without creating ambiguity.

Answer: C. PDA

Answer: C. It has multiple parse trees for some string

Answer: B. Bottom-up parsing

Answer: A. A → BC or A → a

Answer: B. Prove a language is not context-free

Answer: B. Closure under intersection

Answer: A. All regular grammars are context-free

Answer: A. a^n b^n for n ≥ 0

Answer: C. A stack

Answer: B. Describing context-free grammars

Answer: A. Programmable

UTM is programmable to simulate any other Turing machine.

Answer: C. 7

Turing machine has 7-tuple definition.

Answer: C. An automaton with finite control and an infinite tape used as both input and unbounded memory, capable of simulating any effective algorithm.

A Turing machine (TM) is a mathematical abstraction proposed by Alan Turing to capture the intuitive notion of an effective procedure or algorithm. It consists of: • A finite set of states (finite control), including start and possibly accepting/rejecting states. • An infinite tape divided into discrete cells, each cell holding one symbol from a tape alphabet Γ (which contains the input alphabet Σ and a blank symbol ␣). • A tape head that can read and write symbols on the tape and move one cell left or right at each step. A TM configuration is determined by its current state, current tape content, and current head position. A transition function typically has the form: δ : Q × Γ → Q × Γ × {L, R} This means: depending on the current state and tape symbol, the machine writes a new symbol, moves the head left or right, and enters a new state. Why it is powerful: • The infinite tape provides unbounded memory, unlike finite automata or PDA (which has stack but restricted access pattern). • Turing machines can simulate any algorithm that can be executed by a real computer (ignoring resource limitations like time and memory). This leads to the *Church–Turing thesis*: the class of functions that are computable by a TM coincides with the class of functions intuitively computable by any effective method. Variants: • Multi-tape TMs, multi-track tapes, non-deterministic TMs, etc., which are all equivalent in power to the standard TM. They may differ in time complexity but not in the class of decidable languages. TM as language recognizer: • Accepts a string if it eventually enters an accepting state while processing that string, possibly halting. • If it never halts on some input, the language is only *semi-decidable* (recursively enumerable). Thus, the Turing machine is a core model for the theory of computation, providing a benchmark for what can and cannot be computed algorithmically.

Answer: B. A TM that simulates any other TM when given that TM’s description and input as its own input.

A Universal Turing Machine (UTM) is a single Turing machine U that can simulate the behavior of *any* other Turing machine M on any input w, provided that an appropriate encoding of (M, w) is given as input on U's tape. Formally: • Let ⟨M⟩ represent an encoding (as a string) of the description of some TM M (its states, transition function, and so on). • Define a universal machine U such that for all M and w: U(⟨M⟩, w) simulates M(w) • If M halts and accepts w, then U also halts and accepts ⟨M⟩, w. If M halts and rejects, U does the same. If M does not halt, U does not halt. Conceptual significance: • It shows that a single fixed machine can interpret descriptions of programs and execute them, which is essentially what modern stored-program computers do. • Demonstrates that data and programs can be encoded uniformly as strings; a UTM can treat both as input. • This underpins the notion of *software* being data for a general-purpose hardware machine. Encoding: • Turing machines, states, symbols, and transitions are all encoded as strings over some alphabet (e.g., binary) using a systematic scheme. • The universal machine parses this encoding and then simulates transitions of the encoded machine step by step. Church–Turing Thesis connection: • The existence of a UTM supports the idea that all effectively calculable functions can be computed by one fixed machine that takes a program (encoding of an algorithm) and input data. In complexity theory, variants of universal machines are considered when discussing simulation overhead, compilation, and interpretation costs. But from a language-recognition perspective, a UTM is simply a TM that can emulate any other TM when given its description.

Answer: B. Time complexity is the number of steps the TM takes for an input of length n; space complexity is the number of tape cells it scans or writes on for that input.

In complexity theory, for a Turing machine M and an input x of length n = |x|: Time complexity: • The time complexity T_M(n) is defined as the maximum number of steps (state transitions) that M performs on any input of length n, over all inputs of that length. • Formally, T_M(n) = max_{|x|=n} t_M(x), where t_M(x) is the number of steps M takes on input x before halting. • Big-O notation is used: if T_M(n) ≤ c·n^k for large n, we say the algorithm runs in polynomial time O(n^k). Space complexity: • The space complexity S_M(n) is the maximum number of distinct tape cells that M scans or writes on any input of length n (excluding the input portion if you use separate work tapes in multi-tape models). • Formally, S_M(n) = max_{|x|=n} s_M(x), where s_M(x) is the number of cells used during computation. Why they matter: • Time and space give two primary resource measures for the feasibility of algorithms. • Classes like P (problems solvable in polynomial time) and PSPACE (problems solvable in polynomial space) are defined using these measures. • Intractability is often associated with super-polynomial or exponential time complexity, e.g., 2^n, n!. Relationship: • Any TM that uses S(n) space must take at least S(n) time, since each cell used must be visited at least once. • However, a machine can take huge time but very little space (e.g., repeatedly scanning the same small part of the tape). Practical analogies: • Time complexity ~ running time on a real computer. • Space complexity ~ memory consumption. In the context of the course, understanding these notions lets you talk about tractable vs intractable problems, complexity classes, and limitations of computation.

Answer: C. it has the capability to remember arbitrarily long sequences of input symbols

Turing machines are more powerful than FSMs because they have the capability to remember arbitrarily long sequences of input symbols through an unlimited tape. Key differences: (1) FSM - Fixed number of states, limited memory, (2) Turing Machine - States plus unlimited tape, can store and retrieve any amount of information. TM advantages: (1) Infinite tape acts as unlimited memory - Can move back and forth on tape, (2) Can solve undecidable problems that FSMs cannot, (3) Can simulate any algorithm (Church-Turing thesis), (4) Can implement arbitrary computational processes. TM capabilities: (1) Recognize recursively enumerable languages, (2) Compute any computable function, (3) Model any effective procedure. The tape allows: (1) Multiple passes through data, (2) Storage of intermediate results, (3) Complex pattern matching and computation. Incorrect options analysis: (1) "tape movement confined to one direction" - TM can move left or right, (2) "has no finite state" - TM has states, just with unlimited memory, (3) "has finite state" - Both have states. The power comes from unlimited memory (tape), not from the state structure. Practical implications: (1) TMs are theoretical model for computation, (2) Real computers approximate TMs (bounded tape = memory), (3) Some problems are computationally undecidable (halting problem). The TM model is fundamental to computer science theory.

Answer: B. b) Undecidable

The Halting Problem for Turing Machines is Undecidable. This famous problem asks: given any program and input, can we determine if the program will halt (finish) or run forever? Alan Turing proved this is undecidable - no general algorithm exists that can solve this for all programs. This is one of the foundational results in computability theory, showing limits of computation.

Answer: B. Anything that is algorithmically computable

According to the Church-Turing thesis, a Turing machine can compute anything that is algorithmically computable. This thesis (though not formally proven, widely accepted) states that any computation that can be done by any algorithm can be simulated by a Turing machine. It's the foundation for understanding computational theory and the limits of computation. The thesis doesn't restrict to deterministic, polynomial-time, or finite-state problems. It establishes that Turing machines represent the ultimate model of computation—any more powerful model hasn't been discovered.

Answer: B. Any algorithm can be simulated by a Turing machine

Answer: B. Simulate any other Turing machine

Answer: C. Both read and write

Answer: B. Finite control, infinite tape, and read/write head

Answer: C. Number of steps to halt

Answer: A. Polynomial time

Answer: B. Verified in polynomial time

Answer: B. Hard to solve but easy to verify

Answer: B. Whether it halts on a specific input

Answer: C. It is decidable

Answer: B. Undecidable

Answer: B. Bresenham's algorithm

Bresenham's algorithm is the fastest because it uses only integer addition and subtraction.

Answer: C. Touch panel

Touch panel is not purely a physical input device; it serves both input and display output functions.

Answer: D. Graphics Processing Unit (GPU)

Answer: B. Graphical User Interface

GUI = Graphical User Interface for user interaction.

Answer: B. Bresenham's

Bresenham's is fastest using only integer operations.

Answer: B. Real

R represents real numbers in mathematics.

Answer: D. All

Monitor, display controller, and frame buffer all needed for interactive graphics.

Answer: A. Raster-scan draws images as a matrix of pixels, while vector display draws images by directly tracing line segments and curves.

The fundamental distinction lies in how the image is generated and refreshed on the screen: Raster-scan displays: • The screen is divided into a grid of discrete picture elements (pixels). • The display controller scans the screen line by line, from top-left to bottom-right (like reading text), refreshing every pixel at a fixed rate (refresh rate, e.g., 60 Hz, 120 Hz). • The frame buffer (video memory) stores the intensity/color of each pixel. The raster hardware converts this digital information into analog (or digital) signals for the display panel. • Modern monitors (CRT, LCD, LED, OLED) are all raster devices. Computer graphics APIs (OpenGL, DirectX) ultimately target a raster frame buffer. Vector (random-scan) displays: • Instead of scanning every pixel, the electron beam (in CRTs) directly draws geometric primitives (lines, curves) one by one. • The display commands specify endpoints of lines and curves; the hardware deflects the beam along those paths. • There is no fixed pixel grid; resolution can be very high for lines (until limited by the CRT and deflection speed). • These displays were used in early CAD/CAM, oscilloscopes, and specialized graphic terminals. Consequences: • Raster-scan: easier to handle general images (photographs, textures), supports filled regions, anti-aliasing via pixel operations; but needs large frame buffer and bandwidth. • Vector: excellent for crisp line drawings and simple wireframes; limited for filled shapes and shaded images; suffers from flicker when many primitives are drawn (refresh overhead). Architecture of raster-scan system includes: • Frame buffer, • Video controller, • Display device. Vector devices often have a display list of line-drawing commands. For your course, remember: *raster* = pixel grid + frame buffer; *vector* = direct beam tracing of primitives.

Answer: B. b) Position of the electron beam

Vector displays directly control the position of the electron beam. Instead of raster (pixel-based) displays that refresh all pixels, vector displays draw lines by moving the electron beam to specific coordinates. Vectors specify endpoints, and the display draws lines directly between them. This allows efficient drawing of line-based graphics. Vector displays were common in oscilloscopes and early computer graphics. Raster displays eventually replaced them for general-purpose computing.

Answer: B. Phosphor

Phosphor is the coating material used on the screen of a CRT (Cathode Ray Tube) display. The phosphor coating glows (fluoresces) when struck by electrons from the electron beam. Different phosphors have different colors and persistence characteristics. When the electron beam scans across the screen, the phosphor emits light at those points, creating the image. After the beam passes, the phosphor continues to glow briefly (persistence) before fading. This persistence needs to be fast enough to prevent flicker. Phosphor-based displays were the standard for televisions and computer monitors before LCD/LED technology.

Answer: B. Pixel

Answer: B. CRT display

Answer: C. Both A and B

Answer: B. Drawing images line by line

Answer: C. Printer

Answer: B. Graphics API

Answer: B. Pixels

Answer: A. RGB

Answer: B. Pixel color values

Answer: D. Algorithm

Answer: B. Reduce jagged edges in raster images

Answer: B. Representing smooth curves

Answer: B. Parallelogram

Shearing transformation converts a unit square into a parallelogram by shifting one direction relative to another.

Answer: C. Scaling

Scaling transformation resizes objects, potentially in different amounts for different directions (non-uniform scaling).

Answer: C. Browser visible area

Viewport is the visible area of webpage in browser window.

Answer: C. Scaling

Scaling transformation changes object size.

Answer: B. Parallelogram

Shearing transforms square to parallelogram.

Answer: B. 2D

2D rotation occurs in 2D plane.

Answer: C. Shearing

Shearing distorts shape making layers slide over each other.

Answer: B. By multiplying [x y 1]^T with the translation matrix T = [[1 0 0],[0 1 0],[tx ty 1]].

In 2D graphics, homogeneous coordinates are used to represent geometric transformations uniformly as matrix multiplications, which allows composition via matrix multiplication. A 2D point (x, y) is represented in homogeneous form as a 3-component column vector: P = [ x y 1 ]^T The 2D translation by (t_x, t_y) can be written as a 3×3 matrix: T = [ 1 0 0 0 1 0 t_x t_y 1 ] Then the transformed point P' is computed as: P' = P ·? or T · P Be careful with conventions. With column vectors, we typically use: P' = T × P So: [ x' ] [ 1 0 0 ] [ x ] [ x + t_x ] [ y' ] = [ 0 1 0 ] [ y ] = [ y + t_y ] [ 1 ] [ t_x t_y 1 ] [ 1 ] [ 1 ] Thus, homogeneous coordinates allow translation to be handled as a linear operation in 3D space (affine in 2D), whereas in standard 2D coordinates translation is an addition, not representable by a 2×2 matrix alone. Advantages of homogeneous formulation: • Unified framework: translation, rotation, scaling, shear, reflection all expressible as 3×3 matrices. • Composite transformation: applying multiple transforms (e.g., scale then rotate then translate) becomes a single matrix multiplication T_total = T_translate · R · S. • Hardware-friendly: GPUs and graphics pipelines operate with matrix multiplications. Remember the key transformation matrices in homogeneous 2D: • Translation: as above. • Scaling: S = [[Sx 0 0],[0 Sy 0],[0 0 1]]. • Rotation by θ: R = [[cosθ -sinθ 0],[sinθ cosθ 0],[0 0 1]]. • Shear, reflection similarly with proper matrix forms. This homogeneous approach generalizes directly to 3D (4×4 matrices) in the next topic (ACtE0606).

Answer: B. Dx and Dy

A straight line segment is translated by applying translation parameters Dx (horizontal displacement) and Dy (vertical displacement). Translation transformation: (1) New point = Old point + (Dx, Dy), (2) Algebraically: P' = P + T = (x+Dx, y+Dy), (3) Matrix form: [x', y'] = [x, y] + [Dx, Dy]. Properties of translation: (1) Preserves line length and angles, (2) Preserves parallelism, (3) Does not change shape or orientation, (4) Moves all points by same amount. For a line segment with endpoints (x₁, y₁) and (x₂, y₂): (1) New endpoints: (x₁+Dx, y₁+Dy) and (x₂+Dx, y₂+Dy), (2) Length unchanged, (3) Direction unchanged. Translation parameters: (1) Dx - Horizontal shift (positive = right, negative = left), (2) Dy - Vertical shift (positive = up, negative = down). Applications: (1) Computer graphics - Moving objects on screen, (2) CAD systems - Repositioning drawings, (3) Animation - Moving objects over time, (4) Coordinate transformation. Combined transformations: (1) Translate then rotate - Different result than rotate then translate, (2) Multiple translations - Add displacement vectors. The notation P'P'' refers to homogeneous coordinates, and Cy is incorrect. Dx and Dy are the correct parameters for translation.

Answer: A. Transformations that can be done in sequence

Composite transformations refer to transformations that can be applied in sequence to produce combined effects. Concept: (1) Apply one transformation to produce intermediate result, (2) Apply another transformation to the intermediate result, (3) Final result is composite of all transformations. Example sequence: (1) Translate point P to origin (T₁), (2) Rotate around origin (R), (3) Translate back (T₂), (4) Final: P' = T₂(R(T₁(P))). Matrix representation: (1) Composite = M₃ × M₂ × M₁ × P, (2) Single composite matrix = product of individual matrices, (3) Can precompute composite matrix for efficiency. Important property: (1) Matrix multiplication is NOT commutative, (2) Order of transformations matters, (3) Translate-then-rotate ≠ Rotate-then-translate. Applications: (1) Complex object manipulations - Rotation about arbitrary point, (2) Animation sequences - Multiple transformations over time, (3) Hierarchical transformations - Parent-child object relationships, (4) Graphics pipelines - Standard rendering process. Standard composite for rotation about arbitrary point: (1) Translate to origin, (2) Rotate, (3) Translate back. Practical benefits: (1) Efficiency - Single matrix multiplication instead of multiple, (2) Simplicity - Expresses complex operations as sequence of simple ones, (3) Code clarity - Describes intentions step by step. This is fundamental to computer graphics and transformation theory.

Answer: C. c) Angles

Angles are NOT preserved under shear transformation. Shear preserves: (1) Parallelism - parallel lines remain parallel, (2) Area - areas of shapes are preserved, (3) Collinearity - collinear points remain collinear. However, shear does NOT preserve angles - right angles may become acute/obtuse after shearing. This is why shear is useful in graphics for creating italic/slanted text effects.

Answer: A. Centre

To translate a circle to a new point, the Centre should be translated. Translation Concept: (1) Geometric transformation that moves objects, (2) All points move same distance and direction, (3) Preserves shape and size, (4) Defined by translation vector (Δx, Δy). Circle Definition: (1) A circle is defined by center (h, k) and radius r, (2) All points equidistant from center, (3) Equation: (x-h)² + (y-k)² = r². Why Only Centre Needs Translation: (1) Circle defined by two parameters: center and radius, (2) Radius unchanged in translation, (3) Only center position changes, (4) Radius remains the same distance from new center. Translation of Circle: (1) Old circle: center C1(h1, k1), radius r, (2) New circle: center C2(h2, k2), radius r, (3) All points move by vector (h2-h1, k2-k1), (4) Radius unchanged. Mathematical Representation: (1) New center = old center + translation vector, (2) C' = C + T = (h+Δx, k+Δy), (3) Radius r' = r (unchanged). Boundary Points Translation: (1) Outline points also translate by same vector, (2) But not necessary to specify - Center determines circle, (3) Once center translated, circle shape automatically moves. Why Not Other Options: (1) Centre with Radius - Radius stays same, not translated, (2) Outline Points - All move same, redundant to specify all, (3) Radius alone - Wouldn't move circle, changes size. Properties Preserved: (1) Shape - Circle remains circle, (2) Size - Radius unchanged, (3) Orientation - No rotation, (4) Distance - Between any two points same. Application: (1) Computer graphics - Moving shapes, (2) CAD systems - Relocating designs, (3) Animation - Moving objects, (4) Geometric proofs - Transformation properties. Multiple Translations: (1) Can apply multiple translations sequentially, (2) Net effect is sum of vectors, (3) Order doesn't matter (commutative), (4) Inverse translation reverses. This demonstrates transformation geometry principles.

Answer: D. Shear

Shear is the type of transformation that changes the shape of an object. In a shear transformation, one or more coordinates of points are displaced proportionally to other coordinates. Translation moves objects without changing shape or size. Rotation turns objects without changing shape or size. Scaling changes size but preserves proportions (shape). Only shear actually distorts and changes the shape of an object. Shear is used in graphics to create italic/slanted text, skew effects, and perspective corrections. The amount of shear is determined by a shear parameter.

Answer: B. Changes the position of an object

Answer: D. Origin

Answer: B. Changes the size of an object

Answer: D. Shear

Answer: B. Multiple transformations applied in sequence

Answer: A. World coordinates to device coordinates

Answer: A. Line clipping

Answer: A. Removing parts of objects outside the viewing window

Answer: B. Parametric line equations

Answer: B. 3×3

Answer: D. All

3D transformations preserve lines, parallelism, and proportional distances.

Answer: B. 3

There are 3 possibilities for 3D reflection planes. The three principal reflection planes are: (1) XY-plane - reflects across the plane perpendicular to the Z-axis, (2) YZ-plane - reflects across the plane perpendicular to the X-axis, (3) XZ-plane - reflects across the plane perpendicular to the Y-axis. These are the fundamental reflections in 3D graphics. Any other reflection plane can be derived from these. Reflections across these planes are basic transformations in computer graphics and 3D modeling.

Answer: B. Parallel projection

Parallel projection is the type used in isometric drawings. Isometric projection is a form of parallel projection where the three axes are drawn at 120° to each other, and all measurements along the axes are to the same scale. Unlike perspective projection where parallel lines converge to vanishing points, parallel projection maintains all parallel lines as parallel. Isometric drawings are commonly used in technical and engineering drawings because they preserve proportions and are easy to measure. They don't appear as realistic as perspective but are useful for technical documentation.

Answer: B. X, Y, and Z axes

Answer: D. X, Y, or Z axes

Answer: B. Uniform scaling

Answer: A. 3D world coordinates to 2D device coordinates

Answer: B. Parallel lines remain parallel

Answer: B. Parallel lines converge at a vanishing point

Answer: D. Translational

Answer: D. Both B and C

Answer: B. Hidden surface removal

Answer: B. Realistic 3D rendering