# Phil 455: Homework 6

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

1. Here is a formal grammar:

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

Describe in English what set of strings it generates.

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 `*`).

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.

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.

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"

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?
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.)
2. What is the numerical value of the string `"12"`?
3. How would you encode the number fifteen in this system?
4. If `α` encodes the number n in this system, what does `"0" ⁀ α` encode?
5. What does `α ⁀ "0"` encode?

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 ξ {
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.