For each of the following problems (described informally in English), first define a language LC {0,...

Transcribed Image Text:

For each of the following problems (described informally in English), first define a language LC {0, 1}* that formalizes the problem. Then describe the correspondence between: (i) in- stances of the problem with their answers, and (2) strings and their (non-)membership in the language. As an example, consider the problem: "Given a PNG image, which half (top or bottom) most resembles a cat?" A correct answer would be: L = {(I): I is a PNG image whose top half resembles a cat more than its bottom half}. An image I corresponds to the string encoding (I). If I's top half resembles a cat more than its bottom half, then (I) E L; otherwise, (I) L. (a) Given two integers, which one is larger? (You may break ties however you like.) (b) Given a binary string s, does sls (i.e., s concatenated to 1 concatenated to s) have more Os, or more ls? (c) We call a base-2 representation of a positive integer standard if the representation has no leading Os (i.e., it starts with 1). Given a positive integer n, for its standard base-2 representation, which of the following quantities is greater: the sum of the digits, or the product of the digits? (You may break ties arbitrarily.) For each of the following problems (described informally in English), first define a language LC {0, 1}* that formalizes the problem. Then describe the correspondence between: (i) in- stances of the problem with their answers, and (2) strings and their (non-)membership in the language. As an example, consider the problem: "Given a PNG image, which half (top or bottom) most resembles a cat?" A correct answer would be: L = {(I): I is a PNG image whose top half resembles a cat more than its bottom half}. An image I corresponds to the string encoding (I). If I's top half resembles a cat more than its bottom half, then (I) E L; otherwise, (I) L. (a) Given two integers, which one is larger? (You may break ties however you like.) (b) Given a binary string s, does sls (i.e., s concatenated to 1 concatenated to s) have more Os, or more ls? (c) We call a base-2 representation of a positive integer standard if the representation has no leading Os (i.e., it starts with 1). Given a positive integer n, for its standard base-2 representation, which of the following quantities is greater: the sum of the digits, or the product of the digits? (You may break ties arbitrarily.)

Answer rating: 100% (QA)

a Problem Description Given two integers determine which one is larger Formal Language Let Lxyxy are ... View the full answer