Gujarat Technological UniversityWinter 2023 examination

GTU 3151605 Formal Language and Automata Theory Winter 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 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.

Q.1

14 Marks
(a)
3 marks
What is Finite Automata? Differentiate DFA vs. NFA.
(b)
4 marks

Write regular expressions (REs) over alphabet {0, 1}

1Strings start with 0 and has odd length
2Strings have odd length
3Strings end with 1 and not contain 00
4Strings start with 1 and has even length
(c)
7 marks
Draw Finite Automata for following languages:
1L1 = {x | 00 is not substring of x, x ∈ {0,1}*}
2L2 = {x | x ends with 01, x ∈ {0,1}*} Draw FA for L1∪L2L_1 \cup L_2, L1∩L2L_1 \cap L_2 and L1−L2L_1 - L_2

Q.2

14 Marks
(a)
3 marks
Prove that CFG: S → aSbS | bSaS | ε is ambiguous.
(b)
4 marks

Define Context Free Grammar.

1Write CFG for regular expression (a|b)*a(a|b)*a(a|b)*
2Write CFG for equal no. of ‘a’ and ‘b’
(c)
7 marks
Use the pumping lemma to show that following language is not Context Free: L={anbncn∣n≥0}L = \{a^n b^n c^n \mid n \ge 0\}
(c)
7 marks
Design PDA for palindrome with middle symbol ‘c’.

Q.3

14 Marks
(a)
3 marks

Design FAs with Σ = {0, 1} that accept

1The set of all strings with three consecutive 0's.
2The set of all strings those start with ‘1’ and end with ‘0’.
(b)
4 marks
Convert given CFG to CNF.
S → ASB | ε
A → aAS | a
B → SbS | A | bb
(c)
7 marks
Convert NFA to FA using subset construction method. NFA transition table:
qδ(q, a)δ(q, b)
1{2, 3}{4}
2{∅}{4}
3{4}{3}
4{∅}{∅}
(a)
3 marks
Write CFG for balanced parentheses and derive ( ( ) ( ) )
(b)
4 marks
Draw left most derivation tree for string ‘aaabbabbba’ using CFG
S → aB | bA
A → aS | bAA | a
B → bS | aBB | b
(c)
7 marks
Minimize given FA
GTU Formal Language and Automata Theory (3151605) Winter 2023 Question 3 OR (c) Diagram

Q.4

14 Marks
(a)
3 marks
Explain classification of grammar as per Chomsky hierarchy.
(b)
4 marks
Draw right most derivation tree for string ‘aaabbabbba’ using CFG
S → aB | bA
A → aS | bAA | a
B → bS | aBB | b
(c)
7 marks
Conversion from NFA-Λ to FA
qδ(q, Λ)δ(q, 0)δ(q, 1)
A{B}{A}∅
B{D}{C}∅
C∅∅{B}
D∅{D}∅
(a)
3 marks
Differentiate Finite Automata vs. Pushdown Automata
(b)
4 marks
Show that the function f(x, y) = x + y is primitive recursive
(c)
7 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 equivalent PDA.

Q.5

14 Marks
(a)
3 marks
What operations are performed by Turing machine?
(b)
4 marks
Explain the halting problem in brief.
(c)
7 marks
Design a Turing machine for accepting {anbncn∣n≥0}\{a^n b^n c^n \mid n \ge 0\}
(a)
3 marks
Differentiate recursive language vs. recursively enumerable language
(b)
4 marks
Explain Post’s Correspondence Problem (PCP) in brief.
(c)
7 marks
Design a Turing machine for copy a string.

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