UnFoldPrep
Browse Archive
Gujarat Technological UniversitySummer 2025 Examination

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

B.E. · IT Engineering · Semester 5 · Subject Code: 3151605
Download Official GTU PDF
Share:
Total Marks70 MarksExternal theory exam
Passing Marks23 Marks33% minimum cutoff
Exam Duration2.5 Hours2:30 PM – 5:00 PM
Paper Structure5 QuestionsWith internal OR choices
Jump toQ1Q2Q3Q4Q5

Question 1

14 MarksMedium
(a)
Write down 5-tuple definition for the finite automata.
3 Marks
(b)
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
4 Marks
(c)
Draw NFA-^ for the given regular expression: (00+1)*(10)*
7 Marks

Question 2

14 MarksMedium
(a)
Explain procedure to minimize Finite Automata.
3 Marks
(b)
Draw DFA for the string with number of 0s and number of 1s are odd.
4 Marks
(c)
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

7 Marks
OR OPTION
(c)
Convert NFA - ^ to FA:

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

7 Marks

Question 3

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

Question 4

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

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

7 Marks

Question 5

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

Studying for Formal Language and Automata Theory?

Circulate this solved paper with KaTeX formulas and 1-click AI step solvers to your batchmates on WhatsApp or Telegram.

Related papers

About this Examination Paper & Attribution

Official Gujarat Technological University (GTU) examination paper and step-by-step solutions 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 PDF