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 GTU BE/B.Tech 2019 Winter 6th Sem Old 160704 Theory Of Computation Question Paper

Download GTU (Gujarat Technological University) BE/BTech (Bachelor of Engineering / Bachelor of Technology) 2019 Winter 6th Sem Old 160704 Theory Of Computation Previous Question Paper

This post was last modified on 20 February 2020

Tags:GTUBEB.Tech2019 WinterQuestion PaperGujarat Technological University6th SemOld Syllabus160704Theory of ComputationPDFDownload
Download Document
Download Document
GTU BE/B.Tech 2019 Winter Question Papers || Gujarat Technological University


FirstRanker.com

Subject Code: 160704

FirstRanker.com

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

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER- VI (Old) EXAMINATION - WINTER 2019

Date: 11/12/2019

Subject Name: Theory Of Computation

Time: 02:30 PM TO 05:00 PM Total Marks: 70

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

Instructions:

  1. Attempt all questions.
  2. Make suitable assumptions wherever necessary.
  3. Figures to the right indicate full marks.
Q.1 (a) Explain one to one and onto functions with example. Give inverse of the function f: R-> R, f(X) = X? 07
(b) Prove 1+2+3+... + n = (n*(n+1)) / 2 using Principal of Mathematical Induction 07
Q.2 (a) Define Regular Expression. Find Regular Expression corresponding to each of the following subsets of {0,1}*:
  1. The Language of all strings containing exactly two 0’s

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

  2. The Language of all strings that end with 01
  3. The Language of all strings that begin or end with 00 or 11
 07
(b) Draw FAs recognizing following languages, L1 = {x|00 is not a substring of x } L2 = { x| x ends with 01 } Draw FA accepting the language L1 U L2 07
OR
Q.3 (a) Explain Distinguishable strings with example. Draw FA corresponding to a Regular Expression (R.E.) = (11+110)*0, where S = {0,1} 07
(b) Define NFA - ?. Give Recursive Definition of d* for DFA,NFA and NFA — ?. Draw NFA recognizing the language ({0,1}*{10} U {00}*{11}*) * using kleene’s theorem part 1, where S = {0,1} 07
OR
Q.3 (a) Define Pumping Lemma for Regular Languages. Show that following language is not a Regular Language using Pumping Lemma L={0i1i|i>=0}, where S = {0,1} 07
(b) Define CFG. Give CFG for L= {0i 1j 0k |j > i+k } Convert following CFG to Chomsky Normal Form,
  1. S ? AACD
  2. A? aAb|?
  3. C? aC|a

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

  4. D ? aDa|bDb | ?
 07
Q.4 (a) Define PDA. Give DPDA for CFG S ?SS| [S] | {S} |? 07
OR
Q.4 (a) Give Bottom Up PDA for following CFG,
  1. S ? S+T|T
  2. T? T*a|a
 07
(b) Prove that following Grammar is an Ambiguous Grammar S?S+S|S*S|(S)|a Draw parse tree for string a+a*a using above grammar 07
Q.5 (a) Draw Turing Machine (TM) accepting Palindrome over {a,b} 07
(b) Explain following terms
  1. P and NP Completeness
  2. Time and Space Complexity

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

 07
OR
Q.5 (a) Draw Turing Machine (TM) accepting {SS | S ? {a,b}*} 07
(b) Explain unbounded minimization and µ recursive functions 07

FirstRanker.com



This download link is referred from the post: GTU BE/B.Tech 2019 Winter Question Papers || Gujarat Technological University

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

This post was last modified on 20 February 2020