C语言代写|COMP 418/518: Homework 3


Instructions: For this homework, you should work in groups of 2{4 people. Only one member of
the group should submit on Canvas. Specify in your submission the members of your group. The
submission must be typed in LaTeX using the provided template.

Grading: We will give a 5% grade bonus to students taking COMP 418. The homework will be
graded based on correctness, completeness, and quality of writing.

Notation & remarks: For strings x; y 2 A∗, we say that x is a prefix of y, and write x ≤ y, if
xz = y for some z 2 A∗. For example, ab is a prefix of abcde because ab · cde = abcde. Notice that
if x ≤ y then there is a unique extension z 2 A∗ such that xz = y. We write x−1y to denote this
unique extension. For a string x 2 A∗, we write jxj to denote its length. For all strings x; y 2 A∗, it
holds that jx · yj = jxj + jyj. String concatenation satisfies the following left cancellation property:
for all x; y; z 2 A∗, xy = xz implies that y = z.

For sets X and Y , we write X ! Y to denote the set of all functions from X to Y .


• Do not use ellipses in your definitions or your proofs. Instead, use recursive definitions and

• Provide a careful justification of every step in your proofs.

Problem 1 [10 points]

Let A be a set. Show that the prefix relation ≤ on A∗ is a partial order (reflexive, antisymmetric
and transitive).

Solution for 1

Fill me in.

Problem 2 [70 points]

In the lecture of February 18 we discussed denotations (functions) of type A+ ! B and of type
A+ ! B+. Recall that a function f : A+ ! B describes a streaming computation in the following
way: for an input history x 2 A+, the value f(x) is the last output item after consuming x. We call
f an incremental denotation, because it gives us the output increment. A function ’ : A+ ! B+
can sometimes describe a streaming computation in the following way: for an input history x 2 A+,
the value ’(x) is the overall output history after consuming x. We call ’ a cumulative denotation,
because it gives us the cumulative (overall) output.

Remark: In this problem, we are only concerned with streaming computations that produce
exactly one output item per step (i.e., for each input item).

Part A [10 points]

Define an injective function lift from the set A+ ! B to the set A+ ! B+. That is, lift : (A+ !
B) ! (A+ ! B+) and lift is injective. The function lift should convert an incremental denotation
to a cumulative denotation. Provide a proof that lift is injective.

Solution for 2A

Fill me in.

Part B [30 points]

For all sets A and B, find a subset S(A; B) ⊆ (A+ ! B+) so that lift is a one-to-one correspondence
(bijection) from A+ ! B to S(A; B). Provide a proof that lift is a bijection.

Solution for 2B

Fill me in.


本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

E-mail: itcsdx@outlook.com  微信:itcsdx