Tiêu đề 3160704 - TOC 2021W.pdf ✅

1 Seat No.: ________ Enrolment No.___________ GUJARAT TECHNOLOGICAL UNIVERSITY BE - SEMESTER– VI (NEW) EXAMINATION – WINTER 2021 Subject Code:3160704 Date:24/11/2021 Subject Name:Theory of Computation Time:10:30 AM TO 01:00 PM Total Marks: 70 Instructions: 1. Attempt all questions. 2. Make suitable assumptions wherever necessary. 3. Figures to the right indicate full marks. 4. Simple and non-programmable scientific calculators are allowed. MARKS Q.1 (a) Define one-to-one, onto and bijection function 03 (b) The given relation R on set A= {1,2,3} determine whether the 04 Relation is reflexive, symmetric or transitive, give reason. R ={(1,1), (1,2), (1, 3),(2,1), (2, 2), (3, 1),(3,3)} (c) Write Principle of Mathematical Induction. Prove that for 07 every n ≥ 1, 1 + 3 + 5 + ... + (2n - 1) = n2 Q.2 (a) Define FA and Write recursive definition of NFA 03 (b) Find a regular expression of followingsubsets of {0, 1}* 1. The language of all strings that begin or end with 00 or 11. 2. The language of all strings ending with 1 and not containing 00. 04 (c) Draw Finite Automata to accept following over input alphabets Σ ={0, 1} (i) The language accepting strings not ending with ’01’ . (ii)The language accepting strings next to last symbol ‘0’ 07 OR (c) Let M1 and M2 be the FAs pictured in Figure, recognizing languages L1 and L2 respectively. Draw FAs recognizing the following languages. a. L1 U L2 b. L1 - L2 07 Q.3 (a) Give the difference between moore machine and mealy machine. 03 (b) Define Context Free Grammar. Find context-free grammar for the language: L= {aib j c k | j=i+k} 04