Due Date: Wednesday, April 5, 2023.

Reference. The Lisp implementation of the first grammar shown in the lecture : grammar1.el.

For this exercise, choose between the following two options. Option b) counts for achievement A3.

a. In this version of the exercise you will write two functions that print a binary tree in symmetric order (in-order): the left subtree, then the root, and then the right subtree. For example, for the tree discussed in class the symmetric order would be:

18 51 5 33 23 7 10

a.a Write a simple recursive function.

a.b Transform the function into an iterative one using a number of states as in the examples shown in class.

Note. You can find the tree functions discussed in class here (c311_8_rectran.html), the function my-print in part b of this exercise below, and the discussion about mapc and mapcar here (c311_elisp6.html).

b. In this version of the exercise, transform the following function solving the problem of the Towers of Hanoi into an iterative version using the transformation described in class.

Towers of Hanoi. You have 3 vertical poles (towers), one of them starting out with n discs stacked up in decreasing order of size. Thus, you can assume that disc i, with i going form 0 at the base to n-1 at the top, has a radius equal to n-i. The two other poles are empty. You can only move one disc at a time from one pole to another. You cannot stack a disc of larger radius on top of one of smaller size. The goal is to move all the discs from the first tower to the second one, using the third tower as reserve.

In the following recursive version, the operation is accomplished by moving the top n-1 discs from the first tower to the third one using the second as reserve, then moving the largest disc to the second tower, then moving all n-1 discs from the third tower to the second using the first one as reserve. Here is the code:

(defun hanoi (n t1 t2 t3)
  (if (= n 1) ; base case 
      (my-print "move " t1 " " t2 "\n")
    ; else
    (hanoi (- n 1) t1 t3 t2) ; recursive call: notice parameter order
    (my-print "move " t1 " " t2 "\n")
    (hanoi (- n 1) t3 t2 t1))) ; another recursive call

(defun my-print (&rest L)
  "Prints any number of arguments with princ and returns true."
  (mapc 'princ L) t)

The function can be called either as
(hanoi 4 'a 'b 'c) or
(hanoi 4 1 2 3)

The function my-print can be found in the general transformation notes and is discussed in the class slides and notes for this week.

Consider a grammar defined by the following rules, where S, U, and V are non terminals, a, b, and c are terminals, and e stands for the empty string:

S => U
U => b c U 
U => a V
V => a V
V => e

b. Draw the production (parsing) tree for the string   b c b c a a.

c. Which of the following strings are correct from the point of view of the grammar and which ones are not?

b c a b c a
b c b c a a a
a b c a
b c b c b c

d. (*A3) Write a Lisp program that verifies if a list of symbols is correct from the point of view of this grammar. You can use the functions for the grammar discussed in the lecture as model, also found here.

Upload to Canvas, Homework 10, the files in the homework.