THEORY OF COMPUTER SCIENCE (TCS) MAY 2012 COMPUTER SCIENCE SEMESTER 5
Con. 4554-12. GN-8579
(3 Hours) [Total Marks : 100]
N.B.: 1) Question number 1 is compulsory.
2) Attempt any four questions out of remaining six questions.
3) Assumptions made should be clearly stated.
4) Figures to the right indicate full marks.
5) Assume suitable data wherever required but justify the same.
Q.1. a. | State and prove the Pumping Lemma for Regular Language. | (05) |
| b. | Explain the different techniques for Turing Machine Construction. | (05) |
| c. | Compare and Contrast Moore and Mealy Machine. | (05) |
| d. | Prove that it is undecidable whether Context free grammar is ambiguous. | (05) |
Q.2. a. | Write a regular expression for the following languages. | (10) |
| i. The set of all the strings such that the number of 0's is odd. | ||
| ii. The set of all the string that do not contain 1101. | ||
| b. | Convert the following NFA to DFA | (10) |
p is the initial state and r and s are the final state | ||
Q.3. a. | Show that every regular language is context free language | (10) |
| Hint: Construct a CFG by induction on the number of operators in the | ||
| regular expression. | ||
| b. | A Palindrome is a string that equals its own reverse, | (10) |
| such as 0110 or 1011101. Use the pumping lemma to show that | ||
| the set of palindromes is not a regular language. | ||
Q.4. a. | Design a PDA to accept each of the following languages | (10) |
| |  | |
| b. | Convert the grammar | (10) |
| S-> 0AA | ||
| A -> OS|1S|0 | ||
| to a PDA that accepts the same language by empty stack. | ||
Q.5. a. | Begin with the grammar: | (14) |
| S-> ABC|BaB | ||
| A-> aA|BaC|aaa | ||
| B-> bBb|a|D | ||
| C-> CA|AC | ||
| D-> C | ||
| i. Eliminate ϵ Productions. | ||
| ii. Eliminate any unit production in the resulting grammar. | ||
| iii. Eliminate any useless symbols in the resulting grammar. | ||
| iv. Put the resulting grammar into Chomsky Normal Form. | ||
| b. | prove that L={an | n is prime} is not context free. | (06) |
Q.6. a. | Design a Turing Machine for the following language. | (10) |
| "set of all the string of balanced parentheses". | ||
| b. | Convert the following grammar into Greibach Normal Form. | (10) |
| S→ AB1 | 0 | ||
| A→ 00A | B | ||
| B→ 1A1 | ||
Q.7. a. | Myhill-Nerode Theorm. | (05) |
| b. | Post Correspondence Problem. | (05) |
| c. | Universal Turing Machine. | (05) |
| d. | The Classes P and NP. | (05) |
No comments:
Post a Comment