THEORY OF COMPUTER SCIENCE (TCS) DECEMBER 2013 COMPUTER SCIENCE SEMESTER 5
Con. 7047-13. LJ - 11377
(3 Hours) [Total Marks : 100]
(2) Attempt any four questions from remaining six question.
(3) Assumptions made should be clearly stated.
(4) Figure to the right indicate full marks.
| 1. (a) | Define with examples Moore and Mealy machine | 5 |
| (b) | Find the equivalent DFA accepting the regular language defined by right linear | 5 |
| grammer given as:- | ||
| S → aA|bB | ||
| A → aA|bC|a | ||
| B → aB|b | ||
| C → bB | ||
| (c) | State and prove pumping Lemma theorm for regular language. | 5 |
| (d) | Differentiate between Deterministic PDA and Non-deterministic PDA. | 5 |
2. (a) | Design a finite state machine to determine whether a ternary number base 3 is | 10 |
| divisible by 5. [Hint : ∑ = {0,1,2}] | ||
| (b) | Design a Mealy machone for the language {0+1)* (00+11) and convert it to a | 10 |
| Moore machine. | ||
3. (a) | Convert the following NFA with € moves to DFA :- | 10 |
| (b) | Let G be the grammer. G = {(S, X), {a,b}, P, S} where productions are :- | 10 |
| S → aSX|b | ||
| X → Xb|a | ||
| Find:- {i} Leftmost derivation.{ii} Rightmost derivation and | ||
| {iii} Parse tree for the string "aababa". | ||
| 4. (a) | Design turing machine for the language L={anbn|n>=1 | 10 |
| (b) | Design a turing machine to compare the binary number m and n such that if | 10 |
5. (a) | (m>n) output is G, if *(m<n) output is L and when (m=N) output is E. List and explain decision properties of regular language. | 10 |
| Explain the test for checking emptiness of a regular language. | ||
| (b) | Construct left linear and right linear grammer for the regular expression :- | 10 |
| (((01 + 10)* 11)*00)* | ||
6. (a) | Construct a PDA equivalent to following grammar:- | 10 |
| S → oBB | ||
| B → OS|IS|O | ||
| and show the acceptance of 010 by the PDA. | ||
| (b) | Reduce the folowing grammer to Greibach Normal form. | 5 |
| (i) S → AB | ||
| A → BSB|BB|b | ||
| B → a | ||
| (ii) S → 01S|01 | 5 | |
| S → 10S|10 | ||
| S → 00|˄ | ||
7. | Write short notes on (any four) :- | 20 |
| (a) Post Correspondence Problem | ||
| (b) Chomsky Hierarchy | ||
| (c) Universal turing machine | ||
| (d) Recursive and Recursively emurable language | ||
| (e) Classes of complexity |
No comments:
Post a Comment