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

Enrolment No./Seat No_______________ GUJARAT TECHNOLOGICAL UNIVERSITY BE- SEMESTER–VI (NEW) EXAMINATION – WINTER 2024 Subject Code:3160704 Date:20-11-2024 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) Define Finite Automata (FA) with an example. 3 (b) Write regular expressions for the following. (i) Binary numbers that are multiple of 2. (ii) Strings of a's and b's with no consecutive a's . (iii) Strings of a's and b's containing consecutive a's. 4 (c) Construct a DFA for the language over {0, 1}* such that it contains “000” as a substring. 7 Q.2 (a) Define ε-closure(q) with an example. 3 (b) State the difference between NFA and DFA. 4 (c) Prove by pumping lemma, that the language 0 n 1 n is not regular. 7 OR (c) What is ambiguous grammar? Is the following grammar ambiguous? 1. E→ E+E |E*E | id 2. E→ E+E|E*E|(E)|a Justify your answer. 7 Q.3 (a) State the definition of Pushdown automata. 3 (b) Is NPDA (Nondeterministic PDA) and DPDA (Deterministic PDA) equivalent? Illustrate with an example. 4 (c) Construct PDA for the language L={wwR ∣ w∈(a+b)* } 7 OR Q.3 (a) State and prove the pumping lemma for CFL. What is its main application? Give an example. 3 (b) Compare Deterministic PDA and Non deterministic PDA. 4 (c) Is it true that non deterministic PDA is more powerful than that of deterministic PDA? Justify your answer. 7 Q.4 (a) Construct a CFG for set of strings that contain equal number of a’s and b’s over ∑ = {a,b}. 3 (b) What is chomsky normal form? Explain with an example 4 (c) Convert the following grammar G in greibach normal form. 7