CSC262 · TU past paper
Theory of Computation 2078 question paper
The complete TU 2078 exam paper for Theory of Computation (CSC262), all 12 questions with solved model answers written to the mark scheme.
Tap a question to open its answer.
- 110 marksMethod for reduction of NFA to DFAHideAnswer
Give the formal definition of DFA and NFA. How NFA can be converted into equivalent DFA? Explain with suitable example.[10]
--- A DFA is a 5-tuple: $$M = (Q, \Sigma, \delta, q0, F)$$ Where: Component Description ------------------------ $Q$ Finite, non-empty set of states $\Sigma$ Finite set of input symbols (alphabet) $\delta$ Transition function:
- 210 marksNumericalMinimization of Finite State MachinesHideAnswer
Find the minimum state DFA for the given DFA below:
States 0 1 A B F B E C C B D *D E F E B C F B A [10]
Transition table: States 0 1 -------------- A B F B E C C B D D E F E B C F B A - Start state: A - Final state: D - Alphabet: {0, 1} - Final: {D} - Non-final: {A, B, C, E, F} Mark all pairs (X, D) for X in {A,B,C,E,F} as distinguishable:...
- 310 marksEncoding of Turing MachineHideAnswer
Construct a Turing Machine that accepts the language of odd length strings over alphabet {a, b}. Give the complete encoding for this TM as well as its input string w = abb in binary alphabet that is recognized by Universal Turing Machine.[10]
The TM accepts a string if and only if its length is odd. We use a two-state parity tracking approach: the TM scans the input one symbol at a time, toggling between an "odd count" state and an "even count" state. When it hits a blank (en...
- 45 marksAlphabetsHideAnswer
Define the term alphabet, prefix and suffix of string, concatenation and Kleen closure with example. [5]
--- An alphabet is a finite, non-empty collection (set) of symbols. It is usually denoted by Σ. Example: - Σ = {a, b, c} - Σ = {0, 1} --- A string p is called a prefix of a string w if it is obtained by removing zero or more trailing sym...
- 55 marksRegular ExpressionsHideAnswer
Give the regular expressions for the following language over alphabet {a, b}. a. Set of all strings with substring bab or abb. b. Set of all strings whose 3rd symbol is 'a' and 5th symbol is 'b'. [5]
We need all strings over {a, b} that contain bab as a substring, or contain abb as a substring (or both). Step-by-step reasoning: - Any string containing bab: prefix can be any string over {a,b}, then bab, then any suffix over {a,b} - RE...
- 65 marksApplication of Pumping LemmaHideAnswer
Show that L = {ana^nan | n is a prime number} is not a regular language. [5]
Note: The language can be simplified as L = {a^(3n) n is prime}, i.e., strings of a's whose length is 3 times a prime number. --- If A is a regular language, then there exists a pumping length p such that any string s in A with s = p can...
- 75 marksChomsky HierarchyHideAnswer
Explain about the Chomsky's Hierarchy about the language and programs. [5]
Chomsky's Hierarchy (proposed by Noam Chomsky) classifies formal languages and grammars into four levels based on their generative power and the computational model required to recognize them. Each level is a strict subset of the level a...
- 85 marksConstruction of PDA by Final StateHideAnswer
Define a Push Down Automata. Construct a PDA that accepts $L = {a^n b^n \mid n > 0}$. [5]
A Push Down Automata (PDA) is a finite automaton equipped with an additional stack memory. It is a 7-tuple defined as: $$M = (Q, \Sigma, \Gamma, \delta, q0, Z0, F)$$ Where: Component Description ------------------------ $Q$ Finite set of...
- 95 marksChomsky Normal FormHideAnswer
Construct the following grammar into Chomsky Normal Form. S→abSb∣a∣aAbS \rightarrow abSb \mid a \mid aAbS→abSb∣a∣aAbA→bS∣aAAb∣εA \rightarrow bS \mid aAAb \mid \varepsilonA→bS∣aAAb∣ε[5]
$$S \rightarrow abSb \mid a \mid aAbS$$ $$A \rightarrow bS \mid aAAb \mid \varepsilon$$ --- CNF requires every production to be of the form: - $A \rightarrow BC$ (two non-terminals), or - $A \rightarrow a$ (single terminal) --- Identify ...
- 105 marksIntroduction to Turing MachinesHideAnswer
Define Turing Machine and explain its different variations. [5]
A Turing Machine (TM) is a theoretical computational model that consists of an infinite tape divided into cells, a read/write head, and a finite control unit. It is formally defined as a 7-tuple: $$TM = (Q, \Sigma, \Gamma, \delta, q0, B,...
- 115 marksTime and Space complexity of A Turing MachHideAnswer
What do you mean by computational Complexity? Explain about the time and space complexity of a Turing machine. [5]
The complexity of computational problems is discussed by choosing a specific abstract machine as a model of computation and considering how much resource a machine of that type requires for the solution of a given problem. - A Complexity...
- 125 marksIntractabilityHideAnswer
Explain the term Intractability. Is SAT problem is intractable? Justify [5]
Definition: Intractability is a concept in computational complexity theory that classifies problems based on the time and space resources required to solve them. - Problems that can be solved within reasonable time and space constraints ...