UnFoldPrep
Browse Archive
Gujarat Technological UniversityWinter 2025 Examination

GTU 3151605 Formal Language and Automata Theory Winter 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 Hours10:30 AM – 1:00 PM
Paper Structure5 QuestionsWith internal OR choices
Jump toQ1Q2Q3Q4Q5

Question 1

14 MarksMedium
(a)
Define following terms
i)Regular Expression
ii)Regular Grammar
3 Marks
(b)
Write difference between NFA and DFA.
i
4 Marks
(c)
Draw DFA for RE : (0+1)* (01+110)
7 Marks

Question 2

14 MarksMedium
(a)
Define NFA-Λ.
3 Marks
(b)
Write regular expression for the following
i)The language of all strings over {0,1} containing substring 0101.
ii)The language of all strings over {0,1} containing minimum two 0’s..
4 Marks
(c)

Draw an NFA-Λ for the given regular expression without using Kleene’s Theorem : (0+1)*(011+01010)(0+1)*

7 Marks
OR OPTION
(c)

Using subset construction, convert the given NFA to FA accepting the same language.

7 Marks

Question 3

14 MarksMedium
(a)
What language is generated by the given Context free grammar :
i)S → aSa | bSb | Λ
ii)S → aSa | bSb | a | b
3 Marks
(b)
Define Context Free Language (CFL) and prove that every RL is CFL.
4 Marks
(c)
Convert the given CFG into Chomsky normal form.
S →A | B | C
A → aAa | B
B → bB | bb
C → aCaa | D
D → baD | abD |aa
7 Marks
OR OPTION
(a)
What is ambiguous grammar? Explain with suitable example.
3 Marks
(b)
Explain BacosNaur Form (BNF) with example
4 Marks
(c)
Find context free grammar for the following language
i)L = {ai bj ck | i = j + k}
ii)L = { ai bj ck | i = j or i= k}
7 Marks

Question 4

14 MarksMedium
(a)
Define Pumping Lemma for context free languages.
3 Marks
(b)
Show that the given language is not a CFL using pumping lemma.

L = { ai bj ck | i < j < k }

4 Marks
(c)

Construct transition table and diagram for PDA recognizing following language : L = { xcxr | x ϵ {a,b}* }

7 Marks
OR OPTION
(a)

State true or false and justify the same: “Non-deterministic PDA is more powerful than deterministic PDA”.

3 Marks
(b)
Consider the following CFG:
S → AB | Λ
A → aASb | a
B → bS
Give rightmost and leftmost derivation for the string “aaabbb”. Also
draw parse tree for the same.
4 Marks
(c)

Construct transition table and diagram for DPDA recognizing following language : L = { x ϵ {a,b}* | na(x) > nb(x) }

7 Marks

Question 5

14 MarksMedium
(a)
What is Initial Functions?
3 Marks
(b)
What is Bounded Mineralization? Discuss it in detail.
4 Marks
(c)
Write a short note on Universal Turing Machine.
7 Marks
OR OPTION
(a)
Explain primitive recursion function with example
3 Marks
(b)
Discuss undecidable problems with respect to turing machine
4 Marks
(c)

Construct a Turing Machine to accept the language of palindromes over {a, b}.

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 (Winter 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