Scribd
Upload
22 views2 pages

B.Tech Exam: Formal Languages & Automata

This document contains a sample exam paper for a formal languages and automata theory course. It includes: - Two parts (A and B) with Part A being compulsory short answer questions worth 25 marks, and Part B containing 5 units with longer answer questions worth 10 marks each. - Part A includes questions about non-deterministic models, Moore's machines, regular sets, grammars, context-free languages, Turing machines, and complexity classes. - Part B includes questions about DFAs and regular expressions, converting regular expressions to NFAs, properties of regular grammars and languages, context-free grammars, unambiguous languages, pushdown automata, properties of recursively enumerable languages, T

Uploaded by

Dinesh Samala
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
22 views2 pages

B.Tech Exam: Formal Languages & Automata

This document contains a sample exam paper for a formal languages and automata theory course. It includes: - Two parts (A and B) with Part A being compulsory short answer questions worth 25 marks, and Part B containing 5 units with longer answer questions worth 10 marks each. - Part A includes questions about non-deterministic models, Moore's machines, regular sets, grammars, context-free languages, Turing machines, and complexity classes. - Part B includes questions about DFAs and regular expressions, converting regular expressions to NFAs, properties of regular grammars and languages, context-free grammars, unambiguous languages, pushdown automata, properties of recursively enumerable languages, T

Uploaded by

Dinesh Samala
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

Code No: 114AG R13

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD


[Link] II Year II Semester Examinations, May - 2016
FORMAL LANGUAGES AND AUTOMATA THEORY
(Computer Science and Engineering)
Time: 3 Hours Max. Marks: 75

Note: This question paper contains two parts A and B.


Part A is compulsory which carries 25 marks. Answer all questions in Part A.
Part B consists of 5 Units. Answer any one full question from each unit.
Each question carries 10 marks and may have a, b, c as sub questions.

PART - A (25 Marks)

1.a) Define a non-deterministic model with example. [2]


b) State and explain Moors Machine. [3]
c) Give an example to explain the concept of regular set. [2]
d) Discuss about right linear and left linear grammars. [3]
e) Give an example for context free language. [2]
f) Write a context free grammar for the language {0n1n /n>=1}. [3]
g) When do you say that the Turing machine accepts a string. [2]
h) What are the components of a Turing machine? [3]
i) State and explain universal Turing machine. [2]
j) Give an example to explain NP hard and NP Complete problems. [3]
PART - B (50 Marks)

2. Define DFA and Regular expression. DFA accepts all strings corresponding to the
expression 1*01(0+11)*. Also explain how to convert a regular expression to
DFA. [10]
OR
3. Convert the following regular expressions to NFA with epsilon transitions
a) 0*+1101 b) (0+1)* [5+5]

4. Show that if L is regular grammar the L is a regular set. [10]


OR
5. Explain various components of context free grammar and derivation tree in
detail. [10]

6. When do you say a language L is unambiguous? Show that the language


L={anbn|n>=1} is unambiguous. [10]
OR
7. Show that the L is context free language, then there exists a Push down automata
M such that L=N(M). [10]

[Link]
8. Show that any non-trivial property of the recursively enumerable language is
undecidable? [10]
OR
9. Design a Turing machine to accept the set of all palindrome over {0,1}*. Draw a
transition diagram for the Turing machine of the above. [10]

10. State and explain in detail about P and NP problems. [10]


OR
11. Explain what undecidable problem is and post correspondence problem? [10]

--ooOoo--

[Link]

You might also like