--- Content provided by FirstRanker.com ---
GUJARAT TECHNOLOGICAL UNIVERSITY
BE - SEMESTER-VI (NEW) EXAMINATION - WINTER 2018
Subject Code:2160704 Date:27/11/2018
--- Content provided by FirstRanker.com ---
Subject Name:Theory of Computation
Time: 02:30 PM TO 05:00 PM Total Marks: 70
--- Content provided by FirstRanker.com ---
Instructions:
- Attempt all questions.
- Make suitable assumptions wherever necessary.
- Figures to the right indicate full marks.
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
| Q1 (a) | Define one-to-one, onto and bijection function. | 03 |
| (b) | Explain reflexivity, symmetry, and transitivity properties of relations. | 04 |
| (c) | State the principle of mathematical induction and prove by mathematical induction that for all positive integers n 1+2+3+........ +n=n (n+1)/2. | 07 |
| Q2 (a) | What are the closure properties of regular languages? | 03 |
| (b) | Explain moore machine and mealy machine. | 04 |
| (c) | What are the applications of finite automata? Draw Finite Automata to accept following. (1) the language accepting strings ending with 01’ over input alphabets X = {0, 1} --- Content provided by FirstRanker.com --- (i1) the language accepting strings ending with ‘abba’ over input alphabets = {a, b} | 07 |
| OR | ||
| (c) | Define NFA-A. Explain how to convert NFA-A into NFA and FA with suitable example. | 07 |
| Q3 (a) | State pumping lemma for regular languages: | 03 |
| (b) | Explain Union Rule and Concatenation Rule for Context Free Grammar. | 04 |
| (c) | Write difference between DFA and NDFA. Convert the following NDFA to DFA. X | 07 |
| Q3 (a) | Define Context-Sensitive Grammar. What is the language of following context-sensitive grammar? --- Content provided by FirstRanker.com --- S — aTlb | abaT — aaTb | ac. | 03 |
| (b) | Find a regular expression corresponding to each of the following subsets of {0, 1}* (1) The language of all strings that begin or end with 00 or 11. | 04 |
| (c) | What is CNF? Convert the following CFG into CNF. S — ASA | aB, A—B]|S, --- Content provided by FirstRanker.com --- B—ble | 07 |
| Q4 (a) | What is Turing Machine? Write advantages of TM over FSM. | 03 |
| (b) | Define CFG. When a CFG is called an ‘ambiguous CFG’? | 04 |
| (c) | Define PDA. Describe the pushdown automata for language {0"1" | n> 0}. | 07 |
| OR | ||
| Q.5 (a) | Write a short note on Universal Turing Machine. | 03 |
| (b) | Describe recursive languages and recursively enumerable languages. | 04 |
| (c) | Explain push down automata with example and their application in detail. | 07 |
| Q.5 (a) | Define grammar and chomsky hierarchy. | 03 |
| (b) | What are the applications of regular expressions and finite automata? | 04 |
| (c) | Draw a transition diagram for a Turing machine for the language of all palindromes over {a, b}. | 07 |
| OR | ||
| (a) | Compare FA, NFA and NFA-*. | 03 |
| (b) | Write a short note on church-turing thesis. | 04 |
| (c) | Explain primitive recursive function by suitable example. | 07 |
--- Content provided by FirstRanker.com ---
This download link is referred from the post: GTU BE/B.Tech 2018 Winter Question Papers || Gujarat Technological University