Download PTU B-Tech CSE-IT 2020 Dec 7th Sem 71894 Theory Of Computation Question Paper

FirstRanker.com
Firstranker's choice

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

Roll No. Total No. of Pages : 02
Total No. of Questions : 18
B.Tech. (CSE) (2012 to 2017) (Sem.-7)

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

INSTRUCTIONS TO CANDIDATES :

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

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.

SECTION-A

Answer Briefly :

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

1. Differentiate between NFA and DFA.
2. What is a transition graph?
3. What is Chomsky Classification of formal languages?
4. What is a derivation tree?
5. What are the basic operations for strings?

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

6. Define Union of Two Languages.
7. What is ambiguity?
8. Define Mathematical Induction.
9. Define Terminal and Non-Terminal Symbol.
10. Define Leftmost and Rightmost Derivation.

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

FirstRanker.com

SECTION-B

11. Give regular expression to each of the subsets of {a,b} :
    1. Set of all strings containing exactly 2a’s
    2. Set of all strings containing substring aa.

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

12. What is NFA? Show with the help of graph.
13. State pumping lemma for regular sets.
14. What are the steps needed to reduce a context free grammar to an equivalent grammar in Chomsky Normal Form?
15. Discuss the relation between languages and types of automata with help of diagram.

SECTION-C

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

16. Give proof for the statement: If L is a context free language, then we can construct a PDA A accepting L by empty store, i.e. L= N(A).
17. Explain the following :
    1. What are properties of regular languages?
    2. What is Turing machine and its halting problem?
18. Differentiate with example :
    1. Mealy and Moore Machine.

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

    2. CNF and GNF.

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