GTU BE 2019 Summer Question Papers || Gujarat Technological University
Instructions:
--- Content provided by FirstRanker.com ---
GUJARAT TECHNOLOGICAL UNIVERSITY
SEMESTER-VI(NEW) - EXAMINATION - SUMMER 2019
Subject Code:2160704
Subject Name:Theory of Computation
Date:16/05/2019
--- Content provided by FirstRanker.com ---
Time:10:30 AM TO 01:00 PM
Total Marks: 70
- Attempt all questions.
- Make suitable assumptions wherever necessary.
- Figures to the right indicate full marks.
--- Content provided by FirstRanker.com ---
| Q1 (a) | Define 1) Parse tree 2) Ambiguous grammar | MARKS 03 |
| (b) | Prove by mathematical induction: for every n>=1, 1+3+5+ ... +(@2n-1)=n’ | 04 |
| (c) | Consider the grammar: S>ABA, A—>aA|e,B>bB| e Is given grammar ambiguous? If so then remove ambiguity | 07 |
| Q2 (a) | Design Moore machine to generate 1’s complement of binary number. | 03 |
| (b) | Write Regular Expression over the alphabets {a, b} consisting strings:
| 04 |
| (c) | Find context free grammar for the following language. Li={aibjck | i=j +k}, L2= (011+1)* (01)*, L3=(0+1)1*(1+(01)*) | 07 |
| OR | ||
| (c) | Draw FA for following languages:
| 07 |
| Q3 (a) | Find FA accepting languages (i) L1 U L2 and (ii). L1 n L2 Give the left linear grammar for RE (10)°1 | 03 |
| (b) | Minimize the given DFA: --- Content provided by FirstRanker.com --- State / Transition a b> 1 {3} {2} 2 {4} {1} 3 {5} {4} 4 {4} {4} --- Content provided by FirstRanker.com --- 5 {3} {2} | 04 |
| (c) | Eliminate useless symbols, e-productions and unit productions for the following grammar: S>0A0 | 1B1 |BB,A>C,B>S|A,C>S | e | 07 |
| OR | ||
| (c) | Consider the grammar: S>aAS|a A > SbA | SS | ba Derive left most and right most derivation of string aabbaa using given grammar. | 03 |
| (a) | Give CFG for following languages: 1). L =a*b* 2).L={anbn | n>=0} | 04 |
| (b) | Construct finite automata for following left linear grammar: S>X0|Y1 Y=>Y0|1 | 07 |
| Q4 (a) | Compare PDA with FSM | 03 |
| (b) | Write a note on DPDA and NPDA | 04 |
| (c) | Design a pushdown automata to check well-formed parenthesis. | 07 |
| OR | ||
| (c) | Give the formal definition of Turing machine. Also compare the power of DFA, NFA, DPDA, NDPA and TM | 03 |
| (a) | Write a note on post machines. | 04 |
| (b) | Design a Turing machine to reverse the string over alphabet {0, 1} | 07 |
| Q5 (a) | Compare and contrast push down automata and Turing machine. | 03 |
| (b) | Enlist limitations of Turing machines. | 04 |
| (c) | Design a Turing machine which accepts the language consisting string which contain aba as a substring over alphabets {a, b} | 07 |
| OR | ||
| (c) | Discuss universal Turing machine | 03 |
| (a) | Write a short note on Halting problem | 04 |
| (b) | What is decidability? How to prove that the given language is undecidable? List some undecidable problems. | 07 |
This download link is referred from the post: GTU BE 2019 Summer Question Papers || Gujarat Technological University
--- Content provided by FirstRanker.com ---