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 2020 March CSE-IT 7th and 8th Sem BTCS 702 Theory Of Computation Question Paper

Download PTU (I.K. Gujral Punjab Technical University Jalandhar (IKGPTU) ) BE/BTech CSE/IT (Computer Science And Engineering/ Information Technology) 2020 March 7th and 8th Sem BTCS 702 Theory Of Computation Previous Question Paper

This post was last modified on 21 March 2020

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


FirstRanker.com

Roll No. [ ] [ ] [ ] [ ] Total No. of Pages : 02
Total No. of Questions : 18

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

B.Tech.(CSE) (2012 to 2017) (Sem.-7,8)
THEORY OF COMPUTATION
Subject Code : BTCS-702
M.Code : 71894
Time : 3 Hrs. Max. Marks : 60

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

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.

SECTION-A

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

Answer Briefly :

  1. Define Mealy and Moore machines.
  2. Define the term acceptability of a string.
  3. Define pumping lemma for regular sets.
  4. Differentiate between left linear and right linear regular grammar.
  5. --- Content provided by FirstRanker.com ---

  6. Define yield and ambiguity in CFG.
  7. Give example CNF and GNF productions.
  8. Differentiate between deterministic and non-deterministic PDA.
  9. Give rules for converting CFG to PDA.
  10. Give instantaneous description of Turing machine.
  11. --- Content provided by FirstRanker.com ---

  12. What do you mean by halting problem of TM?

SECTION-B

  1. Construct a DFA equivalent to :
    M= ({q0, q1, q2, q3},{0,1}, Ī“, q0, {q3}), where Ī“ is given by following state table :
    State/Z a b
    q0 q0 q1
    q1 q2 q1
    q2 q3 q3
  2. --- Content provided by FirstRanker.com ---

  3. Explain in detail the Chomsky classification of languages.
  4. Define regular sets and write its closure properties.
  5. Prove that P + PQ*Q = a*bQ* where P = b + aa*b and Q is any regular expression
  6. Describe any two representation of TM.
  7. Find a reduced grammar equivalent to the given grammar.

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

    S—> AC|B, A—>a, C—>c|BC, E—>aA|e

SECTION-C

  1. Find a grammar in GNF equivalent to the grammar
    E->E+T|T
    T-> T*F|F

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

    F->(E)|a
  2. Design Turing Machine of {0n1n | n> 1}.
  3. Describe PDA with its representations. Also write rules of converting PDA to CFG.

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 March (All Branches)

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