Download PTU B.Tech 2021 Jan CSE 7th Sem 71894 Theory Of Computation Question Paper

www.FirstRanker.com www.FirstRanker.com

Roll No. _______________________ Total No. of Pages : 02

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

Total No. of Questions: 18

B.Tech.(CSE) (2012 to 2017) (Sem.-7)

THEORY OF COMPUTATION

Subject Code: BTCS-702

M.Code: 71894

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

Time: 3 Hrs. Max. Marks : 60

INSTRUCTION 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.
3. SECTION-C contains THREE questions carrying TEN marks each and students have to attempt ANY TWO questions.

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

SECTION-A

Answer Briefly:

1. Define alphabets in Theory of Computation.
2. Define Non Deterministic Finite Automata.
3. What is a transition table?

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

4. Discuss Regular Expression.
5. State pumping lemma for regular languages.
6. Write short note on decidability.
7. What is left most derivation?
8. Write properties of LR(k) grammars.

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

9. Compare deterministic and non deterministic versions.
10. Define the language of Turing machine.

SECTION-B

1. Define the rule for construction of CFG from given PDA.
2. What are the additional features of PDA compared with NFA?

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

3. Verify whether that the following context free grammar is ambiguous or not :
   S ? 1A0S
   S ? 1A0S1S
   A ? 1
   S ? 0

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

4. Give pushdown automata that recognize the following languages:
   B = {w ? {0, 1}* | w=w^R and the length of w is odd}
5. Describe the recursively Enumerable Language with example?

SECTION-C

1. Write the steps to convert context free grammar into regular expression by taking suitable example?

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

2. Explain the extended transition function for NFA, DFA and ?-NFA. Give the regular expressions for set of all strings that begin with 110?.
3. Write short note on following :
   1. Rules for the conversion of Grammars to PDA
   2. Parsing techniques

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

www.FirstRanker.com