Q.1
14 Marks(a)
Define following terms
i)Regular Expression
ii)Regular Grammar
(b)
Write difference between NFA and DFA.
i
(c)
Draw DFA for RE : (0+1)* (01+110)
Gujarat Technological UniversityWinter 2025 examination
GTU 3151605 Formal Language and Automata Theory Winter 2025 Question Paper & PDF
B.E. · IT Engineering · Semester 5 · Subject code 3151605
- Total
- 70 marks
- To pass
- 23 marks (33%)
- Duration
- 2.5 Hours 10:30 AM – 1: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.
Noted. This paper is in our queue now. Check back tomorrow.
We could not record that here. Email the paper name to hirenjsca@gmail.com and we will add it.
Q.2
14 Marks(a)
Define NFA-Λ.
(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..
(c)
Draw an NFA-Λ for the given regular expression without using Kleene’s Theorem : (0+1)*(011+01010)(0+1)*
OR
(c)
Using subset construction, convert the given NFA to FA accepting the same language.
Q.3
14 Marks(a)
What language is generated by the given Context free grammar :
i)S → aSa | bSb | Λ
ii)S → aSa | bSb | a | b
(b)
Define Context Free Language (CFL) and prove that every RL is CFL.
(c)
Convert the given CFG into Chomsky normal form.
S →A | B | CA → aAa | BB → bB | bbC → aCaa | DD → baD | abD |aaOR
(a)
What is ambiguous grammar? Explain with suitable example.
(b)
Explain BacosNaur Form (BNF) with example
(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}
Q.4
14 Marks(a)
Define Pumping Lemma for context free languages.
(b)
Show that the given language is not a CFL using pumping lemma.
L = { ai bj ck | i < j < k }
(c)
Construct transition table and diagram for PDA recognizing following language : L = { xcxr | x ϵ {a,b}* }
OR
(a)
State true or false and justify the same: “Non-deterministic PDA is more powerful than deterministic PDA”.
(b)
Consider the following CFG:
S → AB | ΛA → aASb | aB → bSGive rightmost and leftmost derivation for the string “aaabbb”. Alsodraw parse tree for the same.(c)
Construct transition table and diagram for DPDA recognizing following language : L = { x ϵ {a,b}* | na(x) > nb(x) }
Q.5
14 Marks(a)
What is Initial Functions?
(b)
What is Bounded Mineralization? Discuss it in detail.
(c)
Write a short note on Universal Turing Machine.
OR
(a)
Explain primitive recursion function with example
(b)
Discuss undecidable problems with respect to turing machine
(c)
Construct a Turing Machine to accept the language of palindromes over {a, b}.
More Formal Language and Automata Theory papers
Questions repeat across sessions. Working through two or three papers shows you which topics GTU asks most.
Other Semester 5 subjects
BE IT
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 (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.