Gujarat Technological UniversitySummer 2023 examination

GTU 3151605 Formal Language and Automata Theory Summer 2023 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 Finite Automata and Pushdown Automata.
(b)
4 marks
What is ambiguous grammar? Does S → aSbS | bSaS | ε ambiguous?
(c)
7 marks
List out the steps involved in pumping lemma for regular language. Prove that L={anbn∣n≥0}L = \{a^n b^n \mid n \ge 0\} is a non-regular language using pumping lemma.

Q.2

14 Marks
(a)
3 marks
Define Context Free Grammar (CFG) with example.
(b)
4 marks
(I) Write CFG which contains at least three times 1 (II) Write CFG that must start and end with same symbol
(c)
7 marks
Convert given NFA into an equivalent FA using subset construction method.
State01
q0{q0}{q0, q1}
q1{q2}{q2}
q2{q3}{q3}
q3∅∅
(c)
7 marks
Draw the Finite Automata recognizing the languages: L1∪L2L_1 \cup L_2, L1∩L2L_1 \cap L_2 and L1−L2L_1 - L_2.
GTU Formal Language and Automata Theory (3151605) Summer 2023 Question 2 OR (c) Diagram

Q.3

14 Marks
(a)
3 marks
Differentiate Finite Automata vs. Pushdown Automata
(b)
4 marks
Given a CFG, G = ({S, A, B}, {0, 1}, P, S) with P as follows:
S → 0B | 1A
A → 0S | 1AA | 0
B → 1S | 0BB | 1
Convert it into an equivalent Pushdown Automata (PDA).
(c)
7 marks
Design a Pushdown Automata (PDA) for L={anb2n∣n≥0}L = \{a^n b^{2n} \mid n \ge 0\}.
(a)
3 marks
Perform leftmost derivation and draw parse tree.
S → A1B
A → 0A | ε
B → 0B | 1B | ε
Output string: 1001
(b)
4 marks
Using Extended Transition Function δ∗\delta^* for FA ({q0, q1, q2, q3}, {0, 1}, {q0}, {q3}, δ). Calculate δ∗(q0,1010010001)\delta^*(q_0, 1010010001).
GTU Formal Language and Automata Theory (3151605) Summer 2023 Question 3 OR (b) Diagram
(c)
7 marks
Design a Pushdown Automata (PDA) for L={anbn+mcm∣n,m≥1}L = \{a^n b^{n+m} c^m \mid n, m \ge 1\}.

Q.4

14 Marks
(a)
3 marks
Write a note on Chomsky Hierarchy.
(b)
4 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 2023 Question 4(b) Diagram
(c)
7 marks
Design a TM for accepting palindrome strings of even & odd length.
(a)
3 marks
Differentiate Recursively Enumerable Language vs. Recursive Language.
(b)
4 marks
Write short note on Universal Turing Machine.
(c)
7 marks
Write a Turing Machine to delete a symbol from tape head position from given string.

Q.5

14 Marks
(a)
3 marks
Show that function f(x, y) = x + y is primitive recursive.
(b)
4 marks
Convert given Context Free Grammar (CFG) to an equivalent Chomsky’s Normal Form (CNF).
S → aAbB
A → Ab | b
B → Ba | a
(c)
7 marks
Prove that If L1 and L2 are context-free languages, then the languages L1∪L2L_1 \cup L_2, L1∩L2L_1 \cap L_2, and L1∗L_1^* are also CFLs.
(a)
3 marks
What are Primitive Recursive Functions?
(b)
4 marks
Explain Post correspondence problem with example.
(c)
7 marks
Convert given NFA-Λ to an equivalent FA.
qδ(q, Λ)δ(q, 0)δ(q, 1)
A{B}{A}∅
B{D}{C}∅
C∅∅{B}
D∅{D}∅

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