CS5170/6070: Assignment 4 [Version 2] 1 Instructions • The assignment comprises of one problem with five sub-parts totalling 20 points, and one problem for two bonus points. If your answer to any question is wrong or incomplete, you will be awarded partial score depending on your attempt. • If you have any questions, post it on canvas. • The assignment is due on Nov 16, 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 days of delay. Thereafter, you’ll receive a zero for the assignment. So any submission after 5:00 PM on Nov 18, 2020 will receive an automatic zero score. If you are submitting after the Nov 14 deadline, email me and cc the TA with the subject [CS5170_Fall2020_Assignment 4] • 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! • The work turned in by you will be considered independent work. The work you submit for evaluation must be your own ideas, thoughts, arguments. Most importantly, it must be described in your own words. 2 Questions Note: For this assignment, assume that a PDA accepts a language by reaching a final state. Q1 Devise PDAs directly (i.e., without going through a CFG) that accept (a) L1 = {0n1k : k > n ≥ 0}. (b) L2 = {0n1k : k > n ≥ 0 and k − 3n is not a multiple of 4}. (c) L3 = {w1w2 : w1, w2 ∈ {0, 1}∗, w1 6= wR2 , and |w1| = |w2|}. (d) L4 = {anbn+2kck : n, k ≥ 0}. (e) L5 = {anbmckbn+m−k : n,m, k ≥ 0 and k ≤ n+m} [4+4+4+4+4 points] 1 3 Bonus Questions Q6 Let us call a binary string w zero-heavy if for every non-empty prefix s of w has at least as many zeros as ones, i.e., #0(s) ≥ #1(s). Let L be the set of all zero-heavy strings. Is L is context-free? If you think it is, provide an NPDA or a CFG in support of L, and if you think it is not, provide a proof of why L is not context-free. Just as an illustration consider 00011, whose non-empty prefixes 0, 00, 000, 0001, 00011 are all zero- heavy; hence 00011 ∈ L. However, 0001111 /∈ L, since 0001111 is a prefix of itself, and 0001111 is not zero-heavy. [2 points] 2
欢迎咨询51作业君