[go: up one dir, main page]
Scribd
Upload
319 views2 pages

Theory of Computation: Instruction To Candidates

This document contains instructions and questions for a Theory of Computation exam consisting of 3 sections - Section A with 10 short answer questions worth 2 marks each, Section B with 4 out of 5 long answer questions worth 5 marks each, and Section C with 2 out of 3 long answer questions worth 10 marks each. The exam covers topics related to formal languages, automata theory and computability theory including regular expressions, context-free grammars, Turing machines, parsing, and more. Students are instructed not to include their mobile number or passing requests on the answer sheet to avoid penalties.

Uploaded by

dheena thayalan
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
319 views2 pages

Theory of Computation: Instruction To Candidates

This document contains instructions and questions for a Theory of Computation exam consisting of 3 sections - Section A with 10 short answer questions worth 2 marks each, Section B with 4 out of 5 long answer questions worth 5 marks each, and Section C with 2 out of 3 long answer questions worth 10 marks each. The exam covers topics related to formal languages, automata theory and computability theory including regular expressions, context-free grammars, Turing machines, parsing, and more. Students are instructed not to include their mobile number or passing requests on the answer sheet to avoid penalties.

Uploaded by

dheena thayalan
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/ 2

Roll No. Total No.

of Pages : 02
Total No. of Questions : 18
B.Tech.(CSE) (2011 Onwards) (Sem.–7,8)
THEORY OF COMPUTATION
Subject Code : BTCS-702
M.Code : 71894
Time : 3 Hrs. Max. Marks : 60

INSTRUCTION TO CANDIDATES :
1. SECTION-A is COMPULSORY consisting of TEN questions carrying T WO marks
each.
2. SECTION-B contains FIVE questions carrying FIVE marks each and students
have to attempt ANY FOUR questions.
3. SECTION-C contains T HREE questions carrying T EN marks each and students
have to attempt ANY T WO questions.

SECTION-A

o m
.r c
Answer briefly :

1.

p e
Justify this statement “L is a subset of closure of alphabet”.

m
2. Define automation.
a o
3.
r p
Acceptability of a string by FA?
.r c
4. b
What is a yield of a derivation tree?
p e
5. What is decidability?
p a
6. Write formal definition of DFA.
b r
7. Define regular expression.

8. Give definition of GNF.

9. List some properties of LR (K) grammars.

10. What is meant by halting problem?

1 | M-71894 (S2)-246
SECTION-B

11. Explain NDPDA and DPDA with the help of example.

12. What do you mean by parsing? How Left most and Right most derivation helps to find
out the ambiguity in a grammar?

13. Explain pumping lemma for Context free languages with the help of example.

14. Explain Chomsky classification of Grammars.

15. What are properties of regular languages?

SECTION-C

16.
o m
What is a context free grammar and explain closure properties of context free grammar?

17. .r c
What are Turing machines? Explain different ways by which we can represent the Turing
machines.

p e m
18. Write short notes on :
a o
r
a. Top Down parsing p .r c
b
b. LR(K) Grammars
p e
c. NFA
p a
d. Recursively enumerable language.
b r

NOTE : Disclosure of Identity by writing Mobile No. or Making of passing request on any
page of Answer Sheet will lead to UMC against the Student.

2 | M-71894 (S2)-246

You might also like