CARLETON UNIVERSITY SCHOOL OF COMPUTER SCIENCE WINTER 2013 COMP. 3803 - DISCRETE STRUCTURES: II ASSIGNMENT III DUE: WEDNESDAY, MAR. 20, 2013 (4:00 PM) ____________________________________________________________________________________ Assignment Policy: Late assignments will not be accepted. You are expected to work on the assignments on your own. Past experience has shown conclusively that those who do not put adequate effort into the assignments do not learn the material and have a probability near 1 of doing poorly on the exams. Important note: When writing your solutions, you must follow the guidelines below. • Please write your name and student number clearly. Your last name must be in Upper Case. • The answers should be concise, clear and neat. Make sure that your TA can read your solutions. • Please submit the solutions in the order of the problems, the solution to Problem 1, then to Problem 2 and so on. • When presenting proofs, every step should be justified so as to get partial credit. • Assignments should be stapled (or in an unsealed envelope) with your name and student number. Substantial departures from the above guidelines will not be graded.. 1. Using the pumping lemma for Regular Languages, prove that the following languages, with the corresponding alphabets are not Regular: • {aNbMa N+M | N, M > 0} • {aN bMa N | N, M > 0} • {aW | W=2N , N > 0} 2. For the alphabet S = {‘(’, ‘)’}, use the pumping lemma for Regular Languages, to prove that the language consisting of matched parenthesis is not Regular. 3. Let S = {0, 1}. Write CFGs that generate the following languages: • {W | W contains no more than three 1’s} • {W | W starts and ends with different symbols} • {W | W starts with a 1 and has an even length} • {W | The length of w is even and its middle two symbols are 01} • {W | W contains twice the number of 0’s than 1’s} • {W | W = 000WR 111, where WR is the reverse of W} 4. Let G = (V, S, R, S) be the context-free grammar, where V = {A, B, S}, S = {0, 1}, S is the start variable, and R consists of the rules S ? 0B|1A1 A ? 11|1S1|BAA B ? 0|0S|AAB • By showing a sequence of productions, prove that 1101111 e L(G). • Prove that L(G) contains the set of non-empty strings W over the alphabet {0, 1} such that the number of 1’s in W is equal to the twice number of 0’s. 5. Convert the following Context Free Grammars (where S = {a, b}) to the Chomsky Normal Form: (a) S ? SS; S ?aSb; S ? e. (b) S ? aSbb; S ? bbSa; S ? e. 6. If L1 is the language generated by the grammar in Question 5 (a), and L2 is the language generated by the grammar in Question 5 (b), create the grammars that generate: • L1 L2 • L1 . L2 • L1 * 7. Find a CFG generating L = {0n 1m 0k 1m | m, n, k = 0}. Give straightforward arguments to show that your answer is right. 8. If a Context Free Grammar G is in the Chomsky Normal Form, how many derivations are required for any string w in L(G).