Scribd
Upload
459 views

Previous Year Question Paper

The document discusses formal languages and automata theory. It contains 8 questions related to topics like NFAs and DFAs, regular expressions, context-free grammars, pushdown automata, Turing machines, and decidability. Some questions ask to construct automata or grammars for specific languages, determine properties of regular languages, and explain concepts like ambiguity and types of Turing machines.

Uploaded by

M2109 DIlshaan Momin
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
459 views

Previous Year Question Paper

The document discusses formal languages and automata theory. It contains 8 questions related to topics like NFAs and DFAs, regular expressions, context-free grammars, pushdown automata, Turing machines, and decidability. Some questions ask to construct automata or grammars for specific languages, determine properties of regular languages, and explain concepts like ambiguity and types of Turing machines.

Uploaded by

M2109 DIlshaan Momin
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

Code No: 155BK R18

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD


B. Tech III Year I Semester Examinations, August - 2022
FORMAL LANGUAGES AND AUTOMATA THEORY
jn
(Common to CSE, IT, ITE)
Time: 3 Hours Max. Marks: 75
tu
Answer any five questions
All questions carry equal marks
---
h
1.a) Differentiate between NFA and DFA.
us
b) Construct DFA for the following language:
i) L={w|w has both an even number of 0’s and even number of 1’s }
ii) L= {w|w is in the form of ‘x01y’ for some strings x and y consisting of 0’s and 1’s}.
ed
[5+10]

2.a) Design a Moore Machine to determine the residue mod 3, where input is treated as
binary.
b) Construct the NFA accepting the following language:
pa
i) The set of all strings over ∑ = {a,b} starting with the prefix “ab”
ii) The set of all strings over {0,1} except those containing the substring “001”. [7+8]
pe
3.a) Construct the NFA for the regular expression r = ((01+10)*00)*.
b) What are the closure properties of regular languages?
c) State the Pumping Lemma for regular sets. [6+5+4]
ra
4.a) Construct the regular expression for the language over the set S={0,1}
i) The set of all strings containing no three consecutive 0’s.
ii) The set of all strings in which the number of occurrences is divisible by 3.
ug
b) Design NFA with epsilon for the RE=(a/b)*ab and convert it into DFA and further find
the minimized DFA. [6+9]

5.a) What do you mean by ambiguity in grammars and languages? How to eliminated
-2
ambiguity in grammars? Explain with an example.
b) Consider the grammar ( {S,A,B}, {a,b}, P, S) that has the productions:
02
S→bA | aB A→bAA | aS | a B→aBB | bS | b.
Find an equivalent grammar in CNF. [7+8]

6.a) Construct the PDA for the following grammar:


2
S→aAA, A→aS | bS | a
b) Discuss the applications of Push down Automata. [8+7]

7. Explain the importance of Turing Machines and also give descriptions of various types
of Turing Machines with necessary examples. [15]

8. Discuss briefly about decidability and undecidability problems. [15]

---oo0oo---

You might also like