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

1 Seat No.: ________ Enrolment No.___________ GUJARAT TECHNOLOGICAL UNIVERSITY BE - SEMESTER–VI (NEW) EXAMINATION – WINTER 2023 Subject Code:3160704 Date:02-12-2023 Subject Name:Theory of Computation Time:02:30 PM TO 05: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) Say whether the statement (p ᴧ (p → q)) → q is tautology or contradiction. 03 (b) The given relation R on set A= {1,2,3} determine whether the Relation 04 is reflexive, symmetric or transitive, give reason. R ={(1,1), (1,2), (2,1), (2, 2), (3,2),(3,3)} (c) Write Principle of Mathematical Induction. And prove for every n ≥ 1, 07 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 not containing substring ‘00’ 07 OR (c) Let M1 and M2 be the FAs pictured in Figure, recognizing languages L1 and L2 respectively. M1-- M2-- Draw FAs recognizing the following languages. a. L1 U L2 b. L1 - L2 07 Q.3 (a) Find context-free grammar for the language: L= {aib j c k | i=j+k} 03 (b) Define mealy machine. Design and mealy machine that gives output ‘x’ if input of sequence is abb, otherwise z. 04 (c) Convert NFA- Λ to FA for following figure. 07
2 OR Q.3 (a) Define Ambiguous grammar. for following grammar say whether the grammar is ambiguous or not. give reason S→ABA, A→aA | Λ , B→bB | Λ 03 (b) Convert the given Moore machine into Mealy machine. Draw state transition diagram of Mealy machine. Present State Next State Output 0 1 →p0 r q0 ɛ p1 r q0 1 q0 p1 s0 0 q1 p1 s0 1 r q1 p1 0 s0 s1 r 0 s1 s1 r 1 04 (c) Find minimum state FA for following figure. 07 Q.4 (a) State pumping lemma for context free language. 03 (b) Construct PDA for S → 0AB A → 1A | 1 B → 0B | 1A | 0 Trace the string 01011 using PDA. 04 (c) Write Kleen’s Theorem part -1. 07 OR Q.4 (a) Define Push Down Automata 03 (b) Using kleene's Theorem Draw NFA-Λ for a given RE aa(ba)*+b*aba* 04 (c) Given the context-free grammar G, find a CFG G’ in Chomsky Normal Form. S -> AaA | CA | BaB A -> aaBa | DC B -> bb | aS C -> Ca | bC | D D -> bD | Λ 07 Q.5 (a) Explain Universal Turing Machine 03 (b) Design a PDA to accept L = {xcy | x, y∈ (a,b)* and |x| = |y|}. 04 (c) Develop a Turing Machine to accept palindromes over {a,b}* 07 OR Q.5 (a) Define grammar and Chomsky hierarchy. 03