辅导案例-CS5170/6070-Assignment 4

欢迎使用51辅导,51作业君孵化低价透明的学长辅导平台,服务保持优质,平均费用压低50%以上! 51fudao.top
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作业君
51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: abby12468