This download link is referred from the post: PTU B.Tech 7th Semester Last 10 Years Previous Question Papers|| Punjab Technical University 2011-2021
Firstranker's choice
--- Content provided by FirstRanker.com ---
| Roll No. | Total No. of Pages : 02 | Total No. of Questions : 18 |
B.Tech (Information Technology) (Sem.-7)
THEORY OF COMPUTATION
Subject Code : BTIT-904 M.Code: 71983
Time: 3 Hrs. Max. Marks : 60
INSTRUCTIONS TO CANDIDATES :
--- Content provided by FirstRanker.com ---
- SECTION-A is COMPULSORY consisting of TEN questions carrying TWO marks each.
- SECTION-B contains FIVE questions carrying FIVE marks each and students have to attempt any FOUR questions.
- SECTION-C contains THREE questions carrying TEN marks each and students have to attempt any TWO questions.
SECTION-A
Write briefly :
--- Content provided by FirstRanker.com ---
- Lā ā*, Justify this formal language expression.
- Define the term 'Automation'.
- What is acceptability of a string by Finite
- What is left recursion?
- What is decidability?
- State Arden's theorem
- Write rules for writing CNF grammar.
- State pumping lemma for CFG.
- What are recursively enumerable languages?
- What is meant by halting problem in TM?
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
Firstranker's choice
SECTION-B
--- Content provided by FirstRanker.com ---
- Explain Chomsky classification of Grammars with help of examples of each.
- What do you mean by parsing? How left most and right most derivation helps to find out the ambiguity in a grammar?
- Explain Chomsky normal form of CFG with the help of example.
- Convert the following NDFA to DFA :
- Find out whether the language L = x" y"z" | n ā„ 1 L = {x"y"z" \ n ā„ 1} is context free or not.
--- Content provided by FirstRanker.com ---
SECTION-C
- What is a context free grammar? Explain closure operties of Context free grammar.
- What are Turing machines? Explain different ways by which we can represent the Turing machines.
- Write a short note on :
- Recursively Enumerable Languages.
- LR(K) Grammars
--- Content provided by FirstRanker.com ---
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.
--- Content provided by FirstRanker.com ---
This download link is referred from the post: PTU B.Tech 7th Semester Last 10 Years Previous Question Papers|| Punjab Technical University 2011-2021