Phil 455: Homework 6

This homework is due by the end of the day on Fri Mar 8 (start of spring break).

Sample answers in purple.

  1. Here is a formal grammar:

    S ⟶    "a" ⁀ S ⁀ "a" S ⟶    "b" ⁀ S ⁀ "b" S ⟶    ""

    Describe in English what set of strings it generates.

    Even palindromes (that is mirror image strings of the form α ⁀ reverse(α)) made only of the letters "a" and "b".

  2. Here is a pattern describing a set of strings: (a|b)*a. Describe those strings in English. Write a formal grammar like the one in Problem 70 that generates those strings with no “shortcuts” (like | or *).

    Strings made of "a"s and/or "b"s, ending with "a".

    The grammar could be:

    S ⟶    "a" S ⟶    "a" ⁀ S S ⟶    "b" ⁀ S

  3. Here is one pattern: (a|ɛ)*. Here is another: a*. Do these describe the same language? Justify your answer. If they don’t, give an example of a string that belongs to one of the languages but not the other.

    Yes, both describe the language whose elements consist of zero or more "a"s.

  4. Here is one pattern: (a|b)*. Here is another: a*|b*. Do these describe the same language? Justify your answer. If they don’t, give an example of a string that belongs to one of the languages but not the other.

    These describe different languages. "ab" belongs to the first language but not the second.

  5. Is every SENTENCE produced by the following grammar a well-formed and meaningful sentence of English? If not, can you give a counter-example? Either way, justify your answer.

    SENTENCE ⟶    NOUN ⁀ "fish" | NOUN ⁀ "fish" ⁀ NOUN NOUN     ⟶    "fish" | "fish" ⁀ NOUN ⁀ "fish"

    Yes. "fish" is a grammatical plural noun phrase, and for any grammatical plural noun phrase α, "fish" ⁀ α ⁀ "fish" is a grammatical plural noun phrase, meaning the fish that α fish. Then, for any grammatical plural noun phrases α and β, α ⁀ "fish" is a grammatical sentence saying that αs participate in the activity of fishing; and α ⁀ "fish" ⁀ β is a grammatical sentence saying that αs participate in fishing, and what they fish for are βs.

    This would for example, generate the sentence "fish fish fish fish fish", either by the parsing [SENTENCE [NOUN fish fish fish] fish [NOUN fish]], meaning that the fish that get fished themselves fish (the hunted are themselves hunters), or by the parsing [SENTENCE [NOUN fish] fish [NOUN fish fish fish]], meaning that the fish that get fished by fish are fished by fish (this is a tautology).

    These two parsings are barely intelligible, but when the sentences get longer they’re more and more difficult to understand. The rules of English described above still seem to apply though. This shows that any string of 2 or more tokens of "fish" concatenated together is a grammatical sentence of English. (So too is the single word sentence "fish", understood as an imperative; but we didn’t include this in our grammar.)

  6. A function f: ℕ → ℕ is monotonically increasing iff for any x, y ∈ ℕ, if x < y then f(x) < f(y). Suppose g is such a function that is also effectively computable/calculable.

    1. Does it follow that the range of g (the subset of ℕ whose members are g’s value for some argument) will be effectively decidable? Justify your answer.
    2. For any decidable subset Δ of ℕ, must there always be some such g (an effectively computable, monotonically increasing function g: ℕ → ℕ whose range is Δ)? Why or why not?
     

    1. Yes. For any n ∈ ℕ, we can decide whether it’s in g’s range as follows. Since g is monotonically increasing, no x > n can be such that g(x) = n. So we can just compute g(x) for each of the finitely many x ≤ n. If any of these results are n, then n is in g’s range; if not then not. (If we compute the results in order of increasing x, and ever get a result > n, then we can stop early and declare we already know that g(x) won’t be n for any greater xs, since g is monotonically increasing.)

    2. Yes. Define g(x) to be the xth element of ℕ (by the familiar ordering) that the decision procedure says is in Δ. For example, if the decision procedure counts 2, 3, and 5 in Δ, but no other number less than 5, then g(3) is computed by first testing 0 and seeing that it’s not in Δ, then testing 1 and getting the same result, then testing 2 and since it’s in Δ, that’s our first hit, 3 is our second hit, 4 is not in Δ so we keep going until we get the third hit which is 5. We let g(3) be this third hit, namely 5. The function g here described will be effectively computable and monotonically increasing, and its range will be Δ.

  7. In earlier classes, we recursively defined the factorial function, using our dissect apparatus. Later we recursively defined other functions that operated on strings instead of numbers. Here’s a variation of one of those string functions, from Homework 5 Problem 58. (The changed parts are italicized.)

    take0 (γ, x) =def dissect γ {     λ β if x = 0! "";     λ "". "0" ⁀ take0("", x - 1);     λ α ⁀ β if isUnit(α). α ⁀ take0(β, x - 1) }

    The original function take returned "" when you requested more letters than γ had to provide, but with this variant we instead return "0"s as the missing letters. So take("21", 4) would be "21", but take0("21", 4) would be "2100".

    In this problem, we’re going to define a multiplication function on natural numbers, but instead of doing it in the style of our factorial definition, where we worked with the numbers directly, we’re going to work instead with numbers encoded as strings of digits. We could work with the decimal/base-10 encoding of numbers into strings of digits, which you’ll be most familiar with, but that would make this exercise longer and more tedious than it needs to be. It’d be more concise to work with, for example, a binary/base-2 number system: then the encoded numbers would be longer, but the functions we wrote to operate on them would be much shorter. The binary system might be a bit too economical, though. Its simplicity may conceal some of what’s going on. So we’ll compromise and work with a “ternary” or base-3 number system. What that means is this. In decimal, the digits range from "0" through "9", and one of the “places” in the string represents “how many ones?”, another represents “how many tens?”, another “how many hundreds?” and so on. In a base-3 encoding, on the other hand, the digits only range from "0" through "2". As before, one of the “places” in the string represents “how many ones?”, but another now represents “how many threes?”, another “how many nines?” and so on.

    Another twist is that, in the collection of string functions we’ve already accumulated, they work from the string’s left side. (That is, take("21010", 2) is "21", not "10".) It will be convenient for this problem to have our numbers encoded correspondingly. We’d like the smallest position, the digit that represents “how many ones?” to come on the left side of the string, and the digit that represents the biggest value to come on the right side of the string. Thus, the number nineteen = 2⋅nine + 0⋅three + 1⋅one would be encoded as "102". This is, then, a backwards base-3 encoding.

    1. With this encoding, what is the numerical value of the string "21"? (Give your answer in decimal or write it out in English.) Five
    2. What is the numerical value of the string "12"? Seven
    3. How would you encode the number fifteen in this system? "021"
    4. If α encodes the number n in this system, what does "0" ⁀ α encode? 3 ⋅ n
    5. What does α ⁀ "0" encode? the same number n encoded by α

    Here is the “scratch work” for a multiplication with decimal digits:

       19
✕  14
-----
   76
+ 19␣
-----
  266

    Here is the same multiplication in our backwards base-3 encoding:

    102
211   ✕
-------
2011
␣102
␣␣102 +
-------
212001

    We’re going to specify some recursive functions that perform this computation. One function mulRow will use the top number ("102") and extract the leftmost digit of the second number ("2") to calculate the first scratch row ("2011"). Then since there are still more digits of the second number to process, it will call mulRow again to handle those remaining. When we call mulRow the second time, one of our inputs will again be the top number ("102"), another will be the remaining digits of the second number ("11"), another will be the sum of all the scratch rows we’ve generated so far (at this point, that’s just "2011"), and finally we have to keep track of the fact that the next scratch row should be shifted one digit to the right.

    We keep going in this way until we’ve handled all the digits of the second number.

    We’re not going to calculate each of the rows "2011", "␣102", and "␣␣102" and only add them up at the end. It will be easier to add them as we go, instead. So our calculation actually looks more like this:

    102 211 ✕ ------- 0 2011 + ------- 2011 ␣102 + ------- 21101 ␣␣102 + ------- 212001

    We are building up to the final result, first getting "2011" from multiplying the leftmost digit "2" of our second argument, next getting "21101" from multiplying the second digit and adding to the result from the previous step as we go, and finally getting "212001" from mutiplying the last digit and adding to the result from the previous step. We’ll call the first argument of our multiplication ("102") the ξ digits, the second argument ("211") the φ digits, and the results we get at each of the steps just described the ζ digits.

    Our function for generating each of these results will look like this:

    mulRow(ξ, φ, ζ, shift) =def dissect φ {
    λ "". ζ;
    λ α ⁀ β if isDigit(α). mulRow(ξ, β, take0(ζ, shift) ⁀ mulCol(...), shift + 1)
}

    isDigit is a function that returns true for "0", "1", "2", and for no other arguments.

    The role of the expression take0(ζ, shift) ⁀ mulCol(...) is to calculate each of the results we mentioned: first "2011", then "21101", then "212001". We’ll discuss how it works in a moment. But assuming that we specify this correctly, then we can request the multiplication of two numbers ξ and φ encoded in our system as mulRow(ξ, φ, "0", 0). The "0" is what we use as the “previous ζ value” at the start of the computation. This diagram may help you:

    The shift argument keeps track of how many positions to the right the multiplication should be shifted as we handle each digit in φ. Our take0(ζ, shift) ⁀ ... amounts to just carrying the initial shift digits of the previous ζ through to the next ζ.

    The mulRow function we end up building will actually let you pass in empty strings for ξ or φ or ζ, treating them as equivalent to "0". You could check for and block that if you wanted to, but we won’t do so.

    You’ll notice that I haven’t supplied the arguments to the invocation of the mulCol function. As you’ll see, that will be your job.

    How does this function mulCol work? It needs to know what the top number ξ to multiply is (in our example, "102"), and also what digit of the second number it’s working with (so first we invoke it with "2", then with "1", then with "1" again). We’ll call each of these digits ψ. It needs to have some part of the previous ζ value to add to the multiplication results to get the next ζ value. Finally, it could turn out as we add up each column to obtain the new ζ value that some of our results need to carry into the next column. For example, when processing the second digit of φ, we end up in the rightmost column adding a "1" and a "2". There is no "3" digit in our numbering system; instead we have to get a result of "0" with a "1" carried to the next column. To keep track of this, mulCol will also take an argument that represents any pending carries that need to be included.

    So our mulCol function will look like this:

    mulCol(ξ, ψ, θ, carry) =def dissect ξ {
    λ "". addCarry(θ, carry);
    λ γ ⁀ δ if isDigit(γ). dissect mulDigit(γ, ψ, take0(θ, 1), carry) {
        λ υ ^ ν if isDigit(υ). υ ⁀ mulCol(...)
    }
}

    This calls two auxiliary functions, addCarry and mulDigit. The first of these adds the single carry digit to the string θ, returning a new version of θ (which will be either the same length or a single digit longer). The second of these takes four single-digit arguments, γ, ψ, η and carry, and returns the two-digit result of multiplying γ⋅ψ and adding to η and carry. For example, mulDigit("2", "2", "2", "1") returns the two-digit encoding "12" of seven. If you want to see definitions of these functions, I’ve provided them; but the details aren’t important. You can rely on them behaving as here described.

    1. At two places above — once in the definition of mulRow and then again in the definition of mulCol — the function mulCol was invoked but I left the arguments unspecified. Demonstrate you understand how these functions are working by filling in those …s.

      Hint: you may want to make use of take0 and/or other string functions we defined in Homework 5.

      The invocation inside mulRow should be mulCol(ξ, α, drop(ζ, shift), "0").

      The invocation inside mulCol should be mulCol(δ, ψ, drop(θ, 1), ν).