Gujarat Technological UniversityWinter 2024 examination

GTU 3151605 Formal Language and Automata Theory Winter 2024 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
Define Deterministic Finite Automata (DFA) and give an example.
(b)
4 marks

Explain the difference between Deterministic Finite Automaton (DFA) and a Nondeterministic Finite Automaton (NFA) with example.

(c)
7 marks

Explore the various closure properties of regular languages, including how the union, intersection, and complement of regular languages can be characterized and computed.

Q.2

14 Marks
(a)
3 marks

Define Regular Expressions. Write the regular expression for the language that accepts all strings over {0,1} ending with 01.

(b)
4 marks

Describe the Pumping Lemma for regular languages. State the lemma and briefly explain how it is used to prove that a language is not regular.

(c)
7 marks

Design a DFA to accept the language L={w|w has both an even number of 0’s and even number of 1’s }

(c)
7 marks

Describe what Epsilon (ε) transitions are in a finite automaton. Illustrate with an example how an NFA with ε transitions can be converted into an equivalent NFA without ε transitions.

Q.3

14 Marks
(a)
3 marks
Define Context-Free Grammar (CFG) and give an example of a CFG.
(b)
4 marks
Explain how ambiguity in a grammar arises with an example.
(c)
7 marks
Consider following grammar:
S → aB / bA
S → aS / bAA / a
A → bS / aBB / b
Give leftmost and rightmost derivations of string w = aaabbabbba.
Also draw the parse tree corresponding to this string.
(a)
3 marks

Define Bacos-Naur Form (BNF). Give an example of a BNF notation representing a simple arithmetic expression grammar.

(b)
4 marks

Explain how unit productions are eliminated from a CFG. Provide an example of a grammar before and after eliminating unit productions.

(c)
7 marks
Define CFG. Write CFG for the following language.
i)L = { aibjck | i,j,k ≥ 0, and i+j = k }
ii)L = { aibjck | i,j,k ≥ 0, and i=j or j=k }

Q.4

14 Marks
(a)
3 marks
Explain intersection and complements of CFL.
(b)
4 marks
Describe Chomsky Hierarchy in brief .
(c)
7 marks

Define Push Down Automata. List out the operations performed on Push Down Automata (PDA). Construct the PDA over alphabet Σ={0,1} for the Language L= {0n1n |n>=0}. Justify your answer.

(a)
3 marks
Explain Context-Free Grammars (CFGs).
(b)
4 marks

Explain difference between "deterministic Pushdown Automaton" (DPDA) and non-deterministic PDAs (NPDAs).

(c)
7 marks

Define Push Down Automata and Construct PDA for L = {aibjck | i,j,k >=0 and i=j or i=k}

Q.5

14 Marks
(a)
3 marks
Explain Recursive Function.
(b)
4 marks
Explain partial, total and constant function.
(c)
7 marks
Construct a Turing machine accepting {xx | x ∈ {a, b}∗}.
(a)
3 marks
Explain Bounded Mineralization.
(b)
4 marks
Explain primitive recursion function with example.
(c)
7 marks
Construct a Turing Machine computing the reverse 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
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 (Winter 2024, 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