CS5170/6070: Assignment 3 [Version 1] 1 Instructions • The assignment comprises of 6 problems totalling 20 points. You can earn 5 bonus points as well if you answer Q7 and Q8. Without details, you will not be awarded partial credit. Ensure you indicate all the steps of your work. • If you have any questions, post it on canvas. • The assignment is due on Oct 30, 2020 by 5:00 PM via Canvas as a single PDF or DOC file. I will not be accepting your work via email. • Late Penalty: You will be assessed a penalty of 5% of your score for each day of delay in your submission for a maximum of 2 additional day of delay. Thereafter, you’ll receive a zero for the assignment. So any submission after 5PM on Sunday 01 Nov 2020 will receive an automatic zero score. If you are submitting after the Friday deadline, email me and cc the TA with the subject [CS5170_Fall2020_Assignment 3] • Any suspicion of cheating will be resolved by asking the student to solve a similar prob- lem. First-time cheaters will result in an automatic zero score for the entire assignment. Repeat offenders will face harsher penalties! 2 Questions Q1 Let L0 be the set complement of the language L = {0n15n : n ≥ 0}. By devising a CFG for L0, establish that L0 is a context-free language. [2 points (1 points each for grammar and for reasoning)] Q2 What is the language generated by the following CF grammar: S → A|D|E A→ 0A0|1A1|B B → 0C1|1C0 C → 0C0|0C1|1C1|1C0|2 D → 0D0|0D1|1D1|1D0|E0|E1|0F |1F E → E0|E1|2 F → 0F |1F |2 Provide detailed explanation. [2 points (1 point for the answer and 1 for reasoning)] Hint: Try to identify a few strings in the language, and see patterns in the derivations as to how the productions are used. There is an underlying structure. Once you identify it, it will help in identifying the language. 1 Q3 Derive the Chomsky normal form for the given grammar: S → 01X|1Y Y X → 00X|λ Y → S|1X|00Z Z → S|X|Y [8 points (2 points for each correct step of the derivation)] Q4 (a) Can left-linear grammars be ambiguous? If yes, give an example, if not, argue why. (b) Argue that languages generated by left-linear grammars cannot be inherently ambiguous. [4 points (1 point each for answer and reasoning in (a) and 2 for (b))]] Q5 Devise a CF grammar for the language L = {0i1j2k : i = 2j or j = 2k or k = 2i}. Assume i, j, k are allowed to be zero or positive numbers. Argue why the grammar accepts the language (in reasonable detail). A complete formal proof is not expected. [2 points] Q6 Use CYK algorithm to determine if w = babbba is a string in the language generated by the following grammar [2 points] S → bAB A→ aA|bB|b B → a|S Indicate all the steps of the algorithm. 3 Bonus Questions Q7 Devise a CF grammar for the language L = {aibj : j = i or i + 4 or i + 8 or · · · or 5i}. Assume i ≥ 0 is allowed. Argue why the grammar accepts the language (in reasonable detail). A complete formal proof is not expected. [3 points] Q8 What is the language generated by the following grammar: [2 points] S → AT |SS|λ A→ 0 B → 1 T → AU U → SX X → BB Provide detailed explanation.
欢迎咨询51作业君
