Put a metric ? on all the words in a dictionary by defining the distance between...

90.2K

Verified Solution

Question

Advance Math

Put a metric ? on all the words in a dictionary by defining thedistance between two distinct words to be 2^?n if the words agreefor the first n letters and are different at the (n+1)st letter. Aspace is distinct from a letter. E.g., ?(car,cart)=2^?3 and?(car,call)=2^?2.
a) Verify that this is a metric.
b) Suppose that words w1, w2 and w3 are listed in alphabeticalorder.
Find a formula for ?(w1,w3) in terms of ?(w1,w2) and ?(w2,w3).

Answer & Explanation Solved by verified expert

4.2 Ratings (597 Votes)

Given Themetric defined on the set of all the words asa To verify that this is a metric we need to check for the fourproperties of a metric space1 Nonnegativity As the metric outputs either0 or 2n both of which are not negative for n0thus nonnegativity holds2 Coincidence Let the distance between twowords say x and y be zeroie Nowas 2n0 for all n012 Hence the distancecan only be zero when xy as in that case the second definition ofthe metric function will hold and the distance will be zeroConversely let xy then by definition Thus the given metric satisfies Hence coincidence holds3 Symmetry Here we consider two cases Firstif xy then clearly Secondly if they are See Answer

Get Answers to Unlimited Questions

Join us to gain access to millions of questions and expert answers. Enjoy exclusive benefits tailored just for you!

Membership Benefits:

Unlimited Question Access with detailed Answers
Zin AI - 3 Million Words
10 Dall-E 3 Images
20 Plot Generations
Conversation with Dialogue Memory
No Ads, Ever!
Access to Our Best AI Platform: Flex AI - Your personal assistant for all your inquiries!

Become a Member