Gujarat Technological UniversitySummer 2025 examination

GTU 3151605 Formal Language and Automata Theory Summer 2025 Question Paper & PDF

B.E. · IT Engineering · Semester 5 · Subject code 3151605
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.

Q.1

14 Marks
(a)
3 marks
Write down 5-tuple definition for the finite automata.
(b)
4 marks
Write regular expressions (REs) over alphabet {0, 1}:
1String should contain exactly two 1’s
2Language of all string containing both 11 and 00 as substring
(c)
7 marks
Draw NFA-^ for the given regular expression: (00+1)*(10)*

Q.2

14 Marks
(a)
3 marks
Explain procedure to minimize Finite Automata.
(b)
4 marks
Draw DFA for the string with number of 0s and number of 1s are odd.
(c)
7 marks
Draw Finite Automata for following languages:

L1={x/x 00 is not substring of x, x ∈ {0,1}*} L2={x/x ends with 01, x ∈ {0,1}*} Draw finite Automata for L1 U L2 and L1-L2

(c)
7 marks
Convert NFA - ^ to FA:

q δ (q,^) δ (q,0) δ(q,1) A {B} {A} Ø B {D} {C} Ø C Ø Ø {B} D Ø {D} Ø

Q.3

14 Marks
(a)
3 marks
Define Context free grammar & context free language.
(b)
4 marks
Write CFG for L={ aibjck | j>i+k}.
(c)
7 marks
Convert following CFG to CNF:
S->aX/Yb
X->S/˄
Y->bY/b
(a)
3 marks
Explain types of derivation and ambiguity.
(b)
4 marks
Write CFG for L={ aibjck | i=j or j=k}.
(c)
7 marks
Convert following CFG to CNF:
S->S(S)/˄

Q.4

14 Marks
(a)
3 marks
Explain deterministic pushdown automata.
(b)
4 marks
Give the difference between top down and bottom up parsing.
(c)
7 marks
Design and draw PDA to accept string with more a’s than b’s.
(a)
3 marks
What is a pushdown automaton? Explain.
(b)
4 marks
Explain conversion from PDA to CFG.
(c)
7 marks

Design and draw deterministic PDA Accepting “Balance string of brackets”.

Q.5

14 Marks
(a)
3 marks
Define Chomsky Hierarchy.
(b)
4 marks
Write a note on Primitive Recursive functions.
(c)
7 marks
Design a Turing machine to delete a symbol.
(a)
3 marks
State the following functions: Partial, Constant and Total.
(b)
4 marks
Define and explain Bounded Quantification.
(c)
7 marks
Design a Turing machine to copy a string.

More Formal Language and Automata Theory 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
Winter 202470 marks · 5 questions
Summer 202470 marks · 5 questions

Other Semester 5 subjects

BE IT

3151604
Object Oriented Analysis and Design
3151606
Web Development
3151608
Data Science

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 Formal Language and Automata Theory (Summer 2025, B.E. · IT Engineering, Sem 5). 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 Formal Language and Automata Theory Papers (7) →Report a typo or correction
ViewDownload PDF