THEORY OF COMPUTER SCIENCE (TCS) DECEMBER 2012 COMPUTER SCIENCE SEMESTER 5
(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.
| 1. (a) | What is finite automation ? Give the finite automation M accepting (a,b)*(baaa). | 5 |
| (b) | Explain Chomsky Hierarchy with languages used, forms of productions in grammars | 5 |
| and accepting device. | ||
| (c) | Differentiate Moore and Mealy machine. | 5 |
| (d) | Give and explain ambiguous context free language. | 5 |
2. (a) | Design finite state machine to add 2 binary numbers of equal length. | 10 |
| (b) | Give the rules for defining languages associated with any regular expression : | 10 |
| Let L1 = all words beginning with a | ||
| L2 = all words ending with a | ||
| what is L1 intersection L2 ? | ||
3. (a) | Give the statement for pumping Lemma for regular languages. | 2 |
| (b) | Construct an NFA-^ for - | |
| (i) (00 + 1) * (10)* | ||
| (ii) ((0 +1)*10 + (00)*(11)*)* | ||
| (c) | Let G be the grammar | |
| S → aB | bA | ||
| A → a | aS | bAA | ||
| B → b | bS | aBB | ||
| Find the leftmost derivation, right most derivation and parse tree for the string | ||
| "bbaaabbaba". | ||
4. (a) | What is TM ? Give the power of TM over FSM. Explain undecidebility and | 10 |
| incompleteness in Turing machine. | ||
| (b) | Explain PDA and power of PDM. Also design the NPDA for given- | 10 |
| CFG | ||
| S → aAA | ||
| A → bS | ||
| A → aS | ||
| S → a | ||
5. (a) | Explain basic Complexity classes. | 6 |
| (b) | Define NP-hard and NP-complete languages. | 4 |
| (c) | Using pumping lemma, check whether an bn is regular or not. | 10 |
6. (a) | How regular expression is converted to DFA ? Explain all rules with example. | 10 |
| (b) | Construct a PDA accepting the language of Palindromes. | 10 |
7. | Write short notes on (any four) :- | 20 |
| (a) Myhill Nerode Theorem | ||
| (b) Universal TM | ||
| (c) Rice Theorem | ||
| (d) Closure properly and decision algorithm for CFL | ||
| (e) Application areas of RE, FA, PDA, CFG, TM. |
No comments:
Post a Comment