Gujarat Technological UniversityWinter 2023 examination

GTU 3160704 Theory of Computation (TOC) Winter 2023 Question Paper & PDF

B.E. · Computer Engineering · Semester 6 · Subject code 3160704
Download official PDFView PDF here
Share with your class
Total
70 marks
To pass
23 marks (33%)
Duration
2.5 Hours 2:30 PM – 5:00 PM
Questions
5 with internal choice
No solutions on this paper yetNeed them for your exam? Ask once. Papers that students ask for are solved first, and we aim to add them within 24 hours.

5 of 25 questions on this paper were also asked in other years. 14 more are types of question GTU sets again with new data. Each is marked below with the years it appeared.See all 34 repeated 3160704 questions, most asked first

Q.1

14 Marks
(a)
3 marks
Say whether the statement (p ᴧ (p → q)) → q is tautology or
contradiction.
(b)
4 marksSame type asked in 2 of 7 papers

The given relation R on set A= {1,2,3} determine whether the Relation is reflexive, symmetric or transitive, give reason. R ={(1,1), (1,2), (2,1), (2, 2), (3,2),(3,3)}

Also asked in Winter 2025 Q1b

(c)
7 marksSame type asked in 3 of 7 papers
Write Principle of Mathematical Induction. And prove for every n ≥ 1,

Also asked in Summer 2026 Q1c, Winter 2025 Q1c

Q.2

14 Marks
(a)
3 marks
Define FA and Write recursive definition of NFA
(b)
4 marksSame type asked in 4 of 7 papers

Find a regular expression of following subsets of {0, 1}*

1The language of all strings that begin or end with 00 or 11.
2The language of all strings ending with 1 and not containing 00.

Also asked in Summer 2026 Q2a, Winter 2025 Q3a, Winter 2024 Q1b

(c)
7 marksSame type asked in 4 of 7 papers
Draw Finite Automata to accept following over input alphabets Σ ={0, 1}
i)The language accepting strings not ending with ’01’ .
ii)The language accepting strings not containing substring ‘00’

Also asked in Summer 2025 Q3a, Winter 2024 Q1c, Summer 2024 Q3a OR

(c)
7 marksSame type asked in 3 of 7 papers

Let M1 and M2 be the FAs pictured in Figure, recognizing languages L1 and L2 respectively. M1-- M2-- Draw FAs recognizing the following languages.

aL1 U L2
bL1 - L2

Also asked in Summer 2026 Q3a, Winter 2025 Q3b

Q.3

14 Marks
(a)
3 marksSame type asked in 5 of 7 papers
Find context-free grammar for the language: L= {aibjck | i=j+k}

Also asked in Summer 2026 Q3c, Winter 2025 Q2b, Summer 2025 Q3c, Summer 2025 Q3b OR, Winter 2024 Q4a

(b)
4 marks

Define mealy machine. Design and mealy machine that gives output ‘x’ if input of sequence is abb, otherwise z.

(c)
7 marksSame type asked in 3 of 7 papers
Convert NFA- Λ to FA for following
GTU Theory of Computation (3160704) Winter 2023 Question 3(c) Diagram

Also asked in Summer 2026 Q2c OR, Summer 2024 Q2c

(a)
3 marksSame type asked in 4 of 7 papers
Define Ambiguous grammar. for following grammar say whether the
grammar is ambiguous or not. give reason
S→ABA, A→aA | Λ , B→bB | Λ

Also asked in Summer 2026 Q3b OR, Winter 2025 Q5a OR, Winter 2024 Q2c OR

(b)
4 marks
Convert the given Moore machine into Mealy machine. Draw state
transition diagram of Mealy machine.
Present
State
Next State Output
0 1
→p0 r q0 ɛ
p1 r q0 1
q0 p1 s0 0
q1 p1 s0 1
r q1 p1 0
s0 s1 r 0
s1 s1 r
(c)
7 marksSame type asked in 3 of 7 papers
Find minimum state FA for following
GTU Theory of Computation (3160704) Winter 2023 Question 3 OR (c) Diagram

Also asked in Summer 2026 Q2c, Winter 2025 Q3c

Q.4

14 Marks
(a)
3 marksAsked in 4 of 7 papers
State pumping lemma for context free language.

Also asked in Winter 2025 Q4a, Summer 2025 Q4a, Summer 2023 Q3b

(b)
4 marksSame type asked in 2 of 7 papers
Construct PDA for
S → 0AB
A → 1A | 1
B → 0B | 1A | 0
Trace the string 01011 using PDA.

Also asked in Summer 2026 Q4b

(c)
7 marks
Write Kleen’s Theorem part -1.
(a)
3 marksAsked in 5 of 7 papers
Define Push Down Automata

Also asked in Winter 2025 Q4b OR, Summer 2025 Q2a, Winter 2024 Q3a, Summer 2023 Q4a

(b)
4 marksSame type asked in 4 of 7 papers
Using kleene's Theorem Draw NFA-Λ for a given RE aa(ba)*+b*aba*

Also asked in Summer 2025 Q2c OR, Summer 2024 Q2c OR, Summer 2023 Q3a

(c)
7 marksSame type asked in 7 of 7 papers
Given the context-free grammar G, find a CFG G’ in Chomsky Normal
Form.
S -> AaA | CA | BaB
A -> aaBa | DC
B -> bb | aS
C -> Ca | bC | D
D -> bD | Λ

Also asked in Summer 2026 Q3c OR, Winter 2025 Q5c OR, Summer 2025 Q3c OR, Winter 2024 Q4c OR, Summer 2024 Q3c OR, Summer 2023 Q3c

Q.5

14 Marks
(a)
3 marksAsked in 2 of 7 papers
Explain Universal Turing Machine

Also asked in Summer 2026 Q5b

(b)
4 marksSame type asked in 3 of 7 papers
Design a PDA to accept L = {xcy | x, y∈ (a,b)* and |x| = |y|}.

Also asked in Summer 2026 Q4c, Winter 2024 Q3c

(c)
7 marksAsked in 3 of 7 papers
Develop a Turing Machine to accept palindromes over {a,b}*

Also asked in Summer 2026 Q5c OR, Winter 2025 Q4c

(a)
3 marksAsked in 2 of 7 papers
Define grammar and Chomsky hierarchy.

Also asked in Summer 2025 Q5b

(b)
4 marksSame type asked in 3 of 7 papers
Design a PDA to accept L = {aibjCk| j = i+k}.

Also asked in Summer 2026 Q4c, Winter 2024 Q3c

(c)
7 marks

Develop a Turing Machine to accept the language L = {X / Na(X)=Nb(X) , X ∈ {a,b}*}

More Theory of Computation papers

Questions repeat across sessions. Working through two or three papers shows you which topics GTU asks most.

Summer 202670 marks · 5 questions
Winter 202570 marks · 5 questions
Summer 202570 marks · 5 questions
Winter 202470 marks · 5 questions

Other Semester 6 subjects

BE Computer

116AG01
Deep Learning and Neural Network
2160701
Software Engineering
2160704
Theory of Computation
2160707
Advanced Java

Preparing with friends?

Send this paper to your class group. Every question has its own link.

About this paper

Official Gujarat Technological University (GTU) examination paper for Theory of Computation (TOC) (Winter 2023, B.E. · Computer Engineering, Sem 6). Features complete 70-mark regular & remedial examination pattern, official marking distribution across all 5 questions, and direct 1-click official PDF download.

Transcribed for student exam preparation from Gujarat Technological University official examination archives. Questions, syllabus guidelines, and curriculum marking schemes remain the intellectual property of Gujarat Technological University.

Download official PDF All Theory of Computation Papers (7) →Report a typo or correction
ViewDownload PDF