THEORY OF COMPUTER SCIENCE (TCS) MAY 2013 COMPUTER SCIENCE SEMESTER 5
Con. 6972-13. GS-9099
(3 Hours) [Total Marks : 100]
(2) Attempt any four questions from remaining six questions.
(3) Draw suitable diagrams wherever necessary.
(4) Assume suitable data, if necessary.
(5) Maximum weightage is given to technical notations.
| 1. (a) | Define the following terms :- | 5 |
| (i) Undecidability | ||
| (ii) Unrestricted grammar | ||
| (iii) Pumping lemma. | ||
| (b) | Define TM and Give its variants. | 5 |
| (c) | Explain Chomsky hierarchy for formal languages. | 5 |
| (d) | Give the closure properties of regular languages. | 5 |
2. (a) | (i) What is ambiguous CFG ? Give one example of ambiguous CFG. | 5 |
| (ii) What is Myhill-Nerode theorem ? Explain necessity of it. | 5 | |
| (b) | Let G be the grammar, find the leftmost derivation , right most derivation and parse | 10 |
| tree for the string 00110101 | ||
| S → OB / 1A | ||
| A → O/OS/1AA | ||
| B → 1/1S/OBB | ||
3. (a) | Explain CNF and GNF with example. | 10 |
| (b) | Give the formal definition of RE and design a DFA corresponding to the regular | 5 |
| expression | ||
| (a+b) * aba (a+b)* | ||
| (c) | Using pumping lemma prove that the following language is regular or not | 5 |
 | ||
| 4. (a) | Write NFA for accepting the following RE | 10 |
| (a+bb)* + ϵ) | ||
| (b) | Explain DPDA and NPDA with languages of them. | 10 |
5. (a) | Find the languages defined by the following grammar : | 10 |
| (i) S → OA/ IC | ||
| A → OS / IB / ϵ | ||
| B → 1A / OC | ||
| C → OB / 1S | ||
| (ii) S → OA / IC | ||
| A → OS / IB | ||
| B → OC / IA / ϵ | ||
| C → OB / IS | ||
| (b) | Construct the PDA accepting following language | 10 |
 | ||
6. (a) | Differentiate between Moore and Mealy machine with proper example and usage | 10 |
| Cary out conversion of Moore MIC to Mealy MIC. | ||
| (b) | Design a Turing machine to accept the language | 10 |
 |
(a) Recursive and recursively enumerable languages
(b) Intractable problems
(c) Simplification of CFGs
(d) Decision properties of regular languages
(e) Rice's theorem.
No comments:
Post a Comment