Download PTU B.Tech 2021 Jan IT 7th Sem 71983 Theory Of Computation Question Paper

Total No. of Pages : 02

B.Tech (Information Technology) (Sem.-7)

THEORY OF COMPUTATION

Subject Code: BTIT-904

--- Content provided by⁠ FirstRanker.com ---

M.Code: 71983

Time: 3 Hrs. Max. Marks : 60

INSTRUCTIONS TO CANDIDATES :

1. SECTION-A is COMPULSORY consisting of TEN questions carrying TWO marks each.
2. SECTION-B contains FIVE questions carrying FIVE marks each and students have to attempt any FOUR questions.

--- Content provided by‌ FirstRanker.com ---

3. SECTION-C contains THREE questions carrying TEN marks each and students have to attempt any TWO questions.

SECTION-A

Write briefly :

1. L ? S*, Justify this formal language expression.
2. Define the term 'Automation'.
3. What is acceptability of a string by Finite Automaton?

--- Content provided by​ FirstRanker.com ---

4. What is left recursion?
5. What is decidability?
6. State Arden's theorem.
7. Write rules for writing CNF grammar.
8. State pumping lemma for CFG.

--- Content provided by FirstRanker.com ---

9. What are recursively enumerable languages?
10. What is meant by halting problem in TM?

SECTION-B

11. Explain Chomsky classification of Grammars with help of examples of each.
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 Chomsky normal form of CFG with the help of example.

--- Content provided by‍ FirstRanker.com ---

14. Convert the following NDFA to DFA :
    
15. Find out whether the language L = {xⁿyⁿzⁿ | n = 1} is context free or not.

SECTION-C

16. What is a context free grammar? Explain closure properties of Context free grammar.
17. What are Turing machines? Explain different ways by which we can represent the Turing machines.

--- Content provided by​ FirstRanker.com ---

18. Write a short note on
    1. Recursively Enumerable Languages.
    2. LR(K) Grammars

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.

FirstRanker.com

--- Content provided by‍ FirstRanker.com ---