FirstRanker Logo

FirstRanker.com - FirstRanker's Choice is a hub of Question Papers & Study Materials for B-Tech, B.E, M-Tech, MCA, M.Sc, MBBS, BDS, MBA, B.Sc, Degree, B.Sc Nursing, B-Pharmacy, D-Pharmacy, MD, Medical, Dental, Engineering students. All services of FirstRanker.com are FREE

📱

Get the MBBS Question Bank Android App

Access previous years' papers, solved question papers, notes, and more on the go!

Install From Play Store

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

Download PTU (I.K.Gujral Punjab Technical University (IKGPTU)) B-Tech (Bachelor of Technology) (CSE-IT)- Computer Science Engineering -Information Technology 2020 December 7th Sem 71894 Theory Of Computation Previous Question Paper

This post was last modified on 13 February 2021

PTU B.Tech Question Papers 2020 December (All Branches)


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

THEORY OF COMPUTATION
Subject Code : BTCS-702
M.Code : 71894
Time : 3 Hrs. Max. Marks : 60

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?
  6. --- Content provided by‍ FirstRanker.com ---

  7. Define Union of Two Languages.
  8. What is ambiguity?
  9. Define Mathematical Induction.
  10. Define Terminal and Non-Terminal Symbol.
  11. Define Leftmost and Rightmost Derivation.
  12. --- Content provided by FirstRanker.com ---

FirstRanker.com

SECTION-B

  1. 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.
  2. --- Content provided by‍ FirstRanker.com ---

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

SECTION-C

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

  1. 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).
  2. Explain the following :
    1. What are properties of regular languages?
    2. What is Turing machine and its halting problem?
  3. Differentiate with example :
    1. Mealy and Moore Machine.
    2. --- Content provided by⁠ FirstRanker.com ---

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


This download link is referred from the post: PTU B.Tech Question Papers 2020 December (All Branches)