GTU · BE Computer · Semester 6
GTU 3160704 Theory of Computation (TOC) Old Question Papers PDF
Official Gujarat Technological University (GTU) old question papers PDF (Regular & Remedial) and step-by-step solved questions for Theory of Computation (TOC) across 2023 – 2026 examinations.
34 questions GTU asked more than onceAsked in all 7 papers: Given the context-free grammar G, find a CFG G’ in Chomsky Normal Form. G : S → aAa | bBb | ^ A → aBb | bBa B → aB | bB | ^See listExam papers
Most repeated questions
34 questions GTU set in two or more of 7 papers, most repeated first. Tap a year to open that paper at the question.
Given the context-free grammar G, find a CFG G’ in Chomsky Normal Form. G : S → aAa | bBb | ^ A → aBb | bBa B → aB | bB | ^
Summer 2026 Q3c OR Winter 2025 Q5c OR Summer 2025 Q3c OR Winter 2024 Q4c OR Summer 2024 Q3c OR Winter 2023 Q4c OR Summer 2023 Q3c
Find context-free grammar for the following language :
Summer 2026 Q3c Winter 2025 Q2b Summer 2025 Q3c Summer 2025 Q3b OR Winter 2024 Q4a Winter 2023 Q3a
Define - Pushdown Automaton and acceptance by a PDA
Winter 2025 Q4b OR Summer 2025 Q2a Winter 2024 Q3a Winter 2023 Q4a OR Summer 2023 Q4a
What is decidability? How to prove that the given language is undecidable? List some undecidable problems.
Winter 2025 Q3c OR Winter 2024 Q5a Summer 2024 Q5a Summer 2023 Q5a
Convert the given regular expression to its equivalent NFA-λ. 𝑟 = 1 + (101)∗ 0 + 01 (01)∗ + 11(101)∗ + 00(11)∗
Summer 2025 Q2c OR Summer 2024 Q2c OR Winter 2023 Q4b OR Summer 2023 Q3a
Check whether the grammar is ambiguous or not ? i. G : S → A | B ii. G : S →aSb | aaSb | ^ A → aAb | ab B → bB | ^
Summer 2026 Q3b OR Winter 2025 Q5a OR Winter 2024 Q2c OR Winter 2023 Q3a OR
Discuss pumping lemma for context-free languages.
Winter 2025 Q4a Summer 2025 Q4a Winter 2023 Q4a Summer 2023 Q3b
Find a regular expression corresponding to each of the following subsets of {0, 1}*. i. The language of all strings that begin or end with 00 or 11. ii. The language of all strings in which every 0 is followed immediately by 11.
Summer 2026 Q2a Winter 2025 Q3a Winter 2024 Q1b Winter 2023 Q2b
Construct a Finite Automata that accepts all strings over {0,1}∗ NOT containing the sub-string 101.
Summer 2025 Q3a Winter 2024 Q1c Summer 2024 Q3a OR Winter 2023 Q2c
Design a Turing Machine that accepts the language of palindromes over {a, b}.
Show 24 more repeated questionsHide the 24 more
Use minimization algorithm to find a minimum-state FA.
Using the subset construction method, convert the following NFA into its equivalent DFA accepting the same language.
Winter 2025 Q2c Winter 2025 Q2c OR Summer 2025 Q2c Summer 2023 Q2c OR
Convert following NFA-^ to an NFA.
Design PDA for the language which accepts balanced strings of brackets { } and [ ].
Summer 2026 Q4c Winter 2024 Q3c Winter 2023 Q5b Winter 2023 Q5b OR
i. Using the principle of Mathematical Induction, Prove that for every n ≥ 1, ii. In following case, a relation on the set {1, 2, 3} is given. Of the three properties, reflexivity, symmetry, and transitivity, determine which ones the relation has. Give reasons. R ={ (1, 1), (2, 2), (3, 3), (1, 2) }
Describe recursively enumerable languages and recursive languages.
Show that L = {ww | w ∈ {0, 1}*} is not context free language.
Define Bounded Minimalization.
Let M1 and M3 be the FAs shown in below figure, recognizing languages L1 and L3 respectively. Draw FAs recognizing the language L1 ∩ L3.
Construct a Turing machine to accept the strings 𝑥. 𝑥𝑟𝑒𝑣
Apply the rules and step by step create a Turing Machine to accept 𝐿 = {𝑎𝑛𝑏𝑛}
Design PDA to accept L = { x ∈ {a, b}* | na(x) > nb(x)}.
Explain the importance of distinguishable strings and equivalent classes’ w.r.t. regular languages.
Write short note on Universal Turing Machine.
Convert the following mealy machine into moore machine.
Construct the equivalent PDA for the following CFG : S → XaY | YbX X → YY | aY | b Y → b | bb
Define - Equivalence relation. Let A = {0, 1, 2, 3} and a relation R on A is defined as R = {(0, 0), (0,
Discuss primitive recursive functions with the help of a suitable example.
Write short note on Church-Turing Thesis.
Discuss the Chomsky hierarchy.
Compare Deterministic PDA and Non deterministic PDA.
What is chomsky normal form? Explain with an example
Discuss μ-recursive functions.
Define ε-closure(q) with an example.
Which branches take this subject
GTU's syllabus lists 3160704 for 2 branches. One set of papers serves all of them.
Semester 6: 2 branches
Computer Engineering, Computer Science & Engineering
Other Semester 6 subjects
Common questions
Are these GTU 3160704 Theory of Computation papers valid for both Regular and Remedial exams?
Yes. Gujarat Technological University (GTU) follows the same 70-mark syllabus, exam blueprint, and 23-mark passing cutoff for both Regular and Remedial (ATKT/backlog) examinations. All 7 past exam sessions (2023 – 2026) serve as comprehensive preparation for either attempt.
How can I download GTU 3160704 Theory of Computation old question papers PDF?
You can download official GTU 3160704 original question paper PDFs directly from the table above with 1 click and zero deceptive ads or wait timers. Every paper also includes interactive online questions with AI study prompts.
What is the passing mark for GTU Theory of Computation (3160704)?
The external theory exam carries 70 marks. The minimum passing cutoff is 23 marks (33%). Exam duration is 2.5 hours.
What is the GTU exam pattern for 3160704?
The examination contains 5 main questions of 14 marks each, totaling 70 marks. Questions 2 through 5 provide internal OR choices, typically split into 3-mark, 4-mark, and 7-mark questions.