Gujarat Technological UniversitySummer 2026 examination

GTU 3151605 Formal Language and Automata Theory Summer 2026 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
Define NFA. How does it differ from DFA?
(b)
4 marks
Write CFG for regular expression (a | b)* a (a | b)* a (a | b)*. Write CFG for (011 | 1)* (01)*
(c)
7 marks
Convert given NFA into an equivalent DFA using subset construction method.
qδ(q, a)δ(q, b)
1{2, 3}{4}
2{∅}{4}
3{4}{3}
4{∅}{∅}

Q.2

14 Marks
(a)
3 marks
Perform leftmost derivation and draw parse tree.
S → A1B
A → 0A | ε
B → 0B | 1B | ε
Output string: 1001
(b)
4 marks
Explain grammar and Chomsky hierarchy.
(c)
7 marks
Convert the following NFA-Λ into NFA and DFA.
GTU Formal Language and Automata Theory (3151605) Summer 2026 Question 2(c) Diagram
(c)
7 marks
Convert the following NFA-Λ into NFA and DFA.
GTU Formal Language and Automata Theory (3151605) Summer 2026 Question 2 OR (c) Diagram

Q.3

14 Marks
(a)
3 marks
Differentiate Finite Automata vs Pushdown Automata
(b)
4 marks
Convert following CFG to Chomsky Normal Form (CNF)
S → AA
A → B | BB
B → abB | b | bb
(c)
7 marks
Draw FA for following languages:
  • L1 = {w | 00 is not substring of w}
  • L2 = {w | w ends in 01} Find FA accepting languages (i) L1 ∪ L2 and (ii) L1 ∩ L2
(a)
3 marks
Prove that the given CFG is ambiguous.
S → S + S | S * S | (S) | a
(b)
4 marks
Convert following CFG to Chomsky Normal Form (CNF)
S → ASB | Λ
A → aAS | a
B → SbS | A | bb
(c)
7 marks
Using recursive definition of δ∗\delta^* in NFA, check acceptability of string 101010 over Σ={0,1}\Sigma = \{0,1\}.
GTU Formal Language and Automata Theory (3151605) Summer 2026 Question 3 OR (c) Diagram

Q.4

14 Marks
(a)
3 marks
Compare and contrast Pushdown Automata and Turing Machine.
(b)
4 marks
Convert given CFG into an equivalent PDA.
S → 0B | 1A
A → 0S | 1AA | 0
B → 1S | 0BB | 1
Check if generated PDA accepts string 001101 or not?
(c)
7 marks
Design a PDA for palindrome over {a, b} with middle symbol X.
(a)
3 marks
What is Primitive Recursive Functions?
(b)
4 marks
Prove that the language L={anbnabn+1∣n=1,2,3,… }L = \{a^n b^n a b^{n+1} \mid n = 1, 2, 3, \dots\} is nonregular using pumping lemma.
(c)
7 marks
Design a PDA to check well-formed parenthesis.

Q.5

14 Marks
(a)
3 marks
Describe recursive languages and recursively enumerable languages.
(b)
4 marks
Define Primitive Recursive Functions and give complete primitive recursive derivations for the function, f:N→Nf : \mathbb{N} \to \mathbb{N} defined by Add(x, y) = x + y.
(c)
7 marks
Draw a Turing Machine that accepts the language {anbncn∣n≥0}\{a^n b^n c^n \mid n \ge 0\} over {a, b, c}.
(a)
3 marks
What is Bounded Mineralization?
(b)
4 marks
Explain Post correspondence problem with example.
(c)
7 marks
Draw a Turing Machine that accepts Even and Odd Palindrome strings 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.

Winter 202570 marks · 5 questions
Summer 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 2026, 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