CSC262 · TU past paper
Theory of Computation 2079 question paper
The complete TU 2079 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 marksEquivalence of DFA and NFAHideAnswer
Show that, for any NFA $N=(Q,\Sigma,\delta,q_0,F)$ accepting language $L=\Sigma^*$, there is a DFA $D=(Q',\Sigma',q_0',\delta',F')$ accepting the same language $L$.[10]
For any NFA N = (Q, Σ, δ, q₀, F) accepting language L, there exists a DFA D = (Q', Σ, δ', q₀', F') such that L(D) = L(N) = L. --- The core insight is that while an NFA can be in multiple states simultaneously, a DFA must be in exactly on...
- 210 marksPumping LemmaHideAnswer
State and prove the Pumping Lemma for regular languages. How can you show with example that pumping lemma is used to prove that a given language is not a regular? Explain.[10]
If A is a regular language, then there exists a pumping length 'p' such that any string 's' where s = p may be divided into three parts s = xyz, satisfying all of the following conditions: 1. xy^i z ∈ A for every i = 0 (the string can be...
- 310 marksNumericalChomsky Normal FormHideAnswer
Given the following expression grammar for simple arithmetic expression with operator + and *. Remove the left recursion from this grammar then simplify and convert to CNF.E→E+T∣TE \rightarrow E+T \mid TE→E+T∣TT→T+F∣FT \rightarrow T+F \mid FT→T+F∣FF→(E)∣aF \rightarrow (E) \mid aF→(E)∣a[10]
The grammar as literally written in the question: $$E \to E+T \mid T$$ $$T \to T+F \mid F$$ $$F \to (E) \mid a$$ Note on interpretation: The problem statement says "operators + and ", but the middle rule is written with + again. The stan...
- 45 marksEpsilon Closure of a StateHideAnswer
Explain the ε\varepsilonε-closure of states on an ε\varepsilonε-NFA with suitable examples. [5]
ε-closure of a state q is the set of all states that can be reached from state q by following zero or more ε (epsilon) transitions, without consuming any input symbol. Formally: ε-closure(q) = { p ∈ Q p is reachable from q using only ε-t...
- 55 marksNumericalReduction of Regular Expression to ε – NFAHideAnswer
Convert the following regular expression into equivalent Finite Automata. a.(0+1)∗10(1+0)a. (0+1)10(1+0)a.(0+1)∗10(1+0)b.1∗0(0+1)∗1b. 10(0+1)*1b.1∗0(0+1)∗1[5]
Two regular expressions to convert to Finite Automata: - (a) $(0+1)^,1,0,(1+0)$ - (b) $1^,0,(0+1)^,1$ Alphabet: $\Sigma = {0, 1}$ for both. --- Break into parts: 1. $(0+1)^$ = any string of 0s and 1s (including empty) 2. $10$ = l...
- 65 marksParse tree and its constructionHideAnswer
Define the term: Parse Tree, left-most and right-most derivation, sentential form and ambiguity with example. [5]
--- A parse tree is a graphical (tree) representation of how a string is derived from a Context Free Grammar (CFG). Formally, given a CFG G = (V, T, P, S), a parse tree has the following properties: - The root is labeled by the start sym...
- 75 marksRepresentation of PDAHideAnswer
Give the formal definition of Push Down Automata. How CFG can be converted into equivalent PDA. Explain with an example. [5]
--- A Pushdown Automaton (PDA) is a 7-tuple: $$M = (Q, \Sigma, \Gamma, \delta, q0, Z0, F)$$ Where: Component Description ------------------------ $Q$ Finite set of states $\Sigma$ Finite set of input symbols (input alphabet) $\Gamma$ Fin...
- 85 marksRegular GrammarsHideAnswer
Define regular grammar. Also explain the method of converting right linear grammar into equivalent finite automata. [5]
--- A regular grammar is a grammar that represents a language which can also be represented by regular expressions. The language generated by a regular grammar is called a regular language, and it is accepted by both NFA and DFA. A regul...
- 95 marksNumericalTuring Machine as a Language RecognizerHideAnswer
Construct a Turing machine that accepts the language, $L = {a^n b^n \mid n \geq 0}$ [5]
- Language: $L = {a^n b^n \mid n \geq 0}$ - Input alphabet: $\Sigma = {a, b}$ - Requirement: construct a TM that accepts (halts in accepting state) exactly the strings with equal numbers of as followed by equal numbers of bs, includi...
- 105 marksIntroduction to Turing MachinesHideAnswer
Define Turing machine and its roles. [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 marksComplexity ClassesHideAnswer
Explain about the complexity classes p, NP and NP-Complete. [5]
P (Polynomial Time) is the class of decision problems that can be solved by a deterministic Turing machine in polynomial time with respect to the input size n. - A problem belongs to P if there exists an algorithm that solves it in O(n^k...
- 125 marksIntractabilityHideAnswer
Write short notes (Any two): a) Big Oh, Big Omega and Big Theta b) Tractable and Intractable Problems c) Chomsky Hierarchy [5]
Short Notes (Any Two)
a) Big Oh, Big Omega, and Big Theta
These are asymptotic notations used to describe the time or space complexity of algorithms as the input size n grows.
1. Big Oh Notation O(g(n)) -- Upper Bound
Definition: f(n) = O(g(n)) if there exist positive constants c and n₀ such that:
f(n) ≤ c · g(n) for all n ≥ n₀
- It gives the worst-case (upper bound) complexity.
- Example: If f(n) = 3n² + 2n, then f(n) = O(n²)
2. Big Omega Notation Ω(g(n)) -- Lower Bound
Definition: f(n) = Ω(g(n)) if there exist positive constants c and n₀ such that:
f(n) ≥ c · g(n) for all n ≥ n₀
- It gives the best-case (lower bound) complexity.
- Example: f(n) = 3n² + 2n, then f(n) = Ω(n²)
3. Big Theta Notation Θ(g(n)) -- Tight Bound
Definition: f(n) = Θ(g(n)) if there exist positive constants c₁, c₂, and n₀ such that:
c₁ · g(n) ≤ f(n) ≤ c₂ · g(n) for all n ≥ n₀
- It gives the average/exact (tight bound) complexity.
- f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n))
- Example: f(n) = 3n² + 2n, then f(n) = Θ(n²)
b) Tractable and Intractable Problems
Tractable Problems
- Problems that can be solved within reasonable time and space constraints are called tractable.
- An algorithm is said to be polynomially bounded if its complexity measure increases with n no more rapidly than a polynomial in n.
- Such problems belong to Class P -- solvable in polynomial time by a deterministic Turing Machine.
- Examples: Sorting, searching, shortest path (Dijkstra's algorithm)
Intractable Problems
- Problems that cannot be solved in polynomial time but require exponential time algorithms are called intractable or hard problems.
- An algorithm is exponentially bounded if its complexity grows exponentially with n.
- Formally, problems are intractable if the time required for any algorithm is at least f(n), where f is an exponential function of n.
- Intractability is the study of problems not solvable in polynomial time.
- Such problems are associated with Class NP -- solvable in polynomial time by a non-deterministic Turing Machine.
- Examples: Travelling Salesman Problem (TSP), 0/1 Knapsack, Hamiltonian Cycle
Feature Tractable Intractable Time complexity Polynomial O(nᵏ) Exponential O(2ⁿ) Class Class P Class NP / NP-Hard Solvability Practically solvable Not practically solvable
c) Chomsky Hierarchy
The Chomsky Hierarchy (proposed by Noam Chomsky) classifies formal grammars and languages into four levels based on their generative power and the type of automaton required to recognize them.
Type Grammar Language Automaton Type 0 Unrestricted Grammar Recursively Enumerable Turing Machine Type 1 Context-Sensitive Grammar (CSG) Context-Sensitive Language Linear Bounded Automaton Type 2 Context-Free Grammar (CFG) Context-Free Language Pushdown Automaton Type 3 Regular Grammar Regular Language Finite Automaton Description of Each Level
Type 3 -- Regular Grammar:
- Productions of the form: A → aB or A → a
- Recognized by Finite Automata (FA)
- Least powerful; used in lexical analysis
Type 2 -- Context-Free Grammar (CFG):
- Productions of the form: A → α (where A is a single non-terminal)
- Recognized by Pushdown Automata (PDA)
- Used in programming language syntax (parsers)
Type 1 -- Context-Sensitive Grammar (CSG):
- Productions of the form: αAβ → αγβ (context matters)
- Recognized by Linear Bounded Automata (LBA)
- More powerful than CFG
Type 0 -- Unrestricted Grammar:
- No restrictions on productions
- Recognized by Turing Machines
- Most powerful; generates recursively enumerable languages
Hierarchy: Type 3 ⊂ Type 2 ⊂ Type 1 ⊂ Type 0