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

Firstranker's choice

FirstRanker.com

Roll No.

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

Total No. of Pages : 02

Total No. of Questions : 18

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

THEORY OF COMPUTATION

Subject Code : BTCS-702

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

M.Code: 71894

Time : 3 Hrs.

Max. Marks : 60

INSTRUCTION TO CANDIDATES :

1. SECTION-A is COMPULSORY consisting of TEN questions carrying TWO marks each.

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

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.

Answer Briefly :

SECTION-A

1. Define alphabets in Theory of Computation.

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

2. Define Non Deterministic Finite Automata.
3. What is a transition table?
4. Discuss Regular Expression.
5. State pumping lemma for regular languages.
6. Write short note on decidability.

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

7. What is left most derivation?
8. Write properties of LR(k) grammars.
9. Compare deterministic and non deterministic versions.
10. Define the language of Turing machine.

SECTION-B

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

11. Define the rule for construction of CFG from given PDA.
12. What are the additional features of PDA compared with NFA?
13. Verify whether that the following context free grammar is ambiguous or not :
    S → 1A0S
    S→ 1A0S1S
    

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

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

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

SECTION-C

16. Write the steps to convert context free grammar into regular expression by taking suitable example?
17. Explain the extended transition function for NFA, DFA and ∈-NFA. Give the regular expressions for set of all strings that begin with 110?.
18. Write short note on following :
    1. Rules for the conversion of Grammars to PDA
    2. Parsing techniques

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