Assignment 3. Due January 17. Total points: 40 ---------------------------------------------------------- 1. (4 points) Let insert(Number, List1, List2) be a ternary predicate that succeeds if and only if its third argument, a sorted list of numbers 'List2' is obtained from its second argument, also a sorted list of numbers 'List1', by inserting 'Number' in the proper place. (The lists are sorted in ascending order.) Assume it is implemented as follows: insert(X, [H|T1], [H|T2]) :- X>H, !, insert(X, T1, T2). insert(X, L, [X|L]). a. Provide an appropriate query to show that this program is incorrect with respect to the given specification. b. Change the program so that it works correctly. ====================== 2. (4 points) (a) Compute E\theta, where E=f(x,f(x,b,y),g(a,z)) and \theta= {x -> y, y -> g(a,z), z -> x\}. (b) Compute \theta\sigma, where \theta={x -> f(x), y -> z, z -> g(a,y,h(x))} and \sigma= {x -> y, z -> y, y -> h(y), w -> a}. (c) Compute \theta\theta, where \theta={x -> f(x), y -> z, z -> g(a,y,h(x))}. (d) Which of the following terms is more general than the others? f(g(x),g(y)), f(g(x),y), f(g(y),x), f(g(x),g(x)) Justify your answer by showing the corresponding substitutions. REMARK. A term t is more general than a term s if s is an instance of t, i.e., if there is a substitution \theta such that t\theta = s. ========================= 3. (4 points) Sketch the steps of the unification algorithm discussed in the class on the pairs of terms below: a) f(a,x,g(y)) and f(z,y,x) b) f(x,y,z,w) and f(f(u,u),f(x,x),f(y,y),f(z,z)) Here f,g,a,b,c,d are function symbols, x,y,z,u,w are variables. ======================= 4. (6 points) Implement the predicate occurs(Var, Term) that succeeds if the Prolog variable Var occurs in the Prolog term Term, and fails otherwise. Hint 1. You can use var(term) to check whether term is a Prolog variable. Hint 2. You can use var1 == var2 to check whether 'var1' and 'var2' are identical. Sample runs: ?- occurs(X, f(X)). true. ?- occurs(X, f(Y)). false. ?- occurs(X, f(a,g(b,h(X,c),d))). true. ?- occurs(X, X). true. ?- occurs(x, f(x)). false. ?- occurs(x, x). false. ?- occurs(x, f(X)). false. ========================== 5. (6 points) Generate all triples (X,Y,Z) that satisfy the conditions that all three components are different integers between 0 and 9 (both included), and that (10*X+Y)/(10*Y+Z) equals X/Z. The output of your program should be to the screen, and be in the form: 3 5 9 3 1 6 if (3, 5, 9) and (3, 1, 6) happen to be the solutions. (Usage of the 'findall' predicate is permitted.) ======================== 6. (8 points) Implement the predicate unify(term1, term2, mgu) that succeeds if 'mgu' is a most general unifier of 'term1' and 'term2'. Use the algorithm discussed in the class. Requirements: - term1 and term2 do not contain Prolog variables. If they do, your program should print: Error: The input terms should not contain Prolog variables. and fail. (You can use var(term) to decide whether 'term' is a Prolog variable.) - The variables in term1 and term2 are Prolog atoms that start with x, y, or z. (You can use the built-in atom_chars predicate to decide whether an atom starts with x, y, or z) - mgu is a list of the form [v1 --> t1, ... , vn --> tn] where v1, ..., vn are variables that occur in term1 or term2 and t1, ..., tn are terms. Use the 'op' declaration to be able to write --> as an infix operator. (Consult Section 5.5, Declaring Operators, from the book or the system manual for explanations how to declare operators in the program.) Sample runs (the order of elements in the output Mgu list does not matter): ?- unify(f(x,g(a)), f(b,g(y)), Mgu). Mgu = [y --> a, x --> b]. ?- unify(f(X,g(a)), f(b,g(y)), Mgu). Error: The input terms should not contain Prolog variables. false. ?- unify(f(x,g(a)), f(b,g(x)), Mgu). false. ?- unify(f(x), f(g(x)), Mgu). false. ?- unify(f(x), g(a), Mgu). false. ?- unify(f(x,x), f(y,g(y)), Mgu). false. ?- unify(f(x,x), f(y,g(z)), Mgu). Mgu = [y --> g(z)), x --> g(z))]. ?- unify(f(x1,x2,x3,g(y0,y0),g(y1,y1),g(y2,y2),y3), f(g(x0,x0),g(x1,x1),g(x2,x2),y1,y2,y3,x3), Mgu). Mgu = [y0 --> x0, y2 --> g(g(x0, x0), g(x0, x0)), x3 --> g(g(g(x0, x0), g(x0, x0)), g(g(x0, x0), g(x0, x0)))), x1 --> g(x0, x0), x2 --> g(g(x0, x0), g(x0, x0)), y1 --> g(x0, x0), y3 --> g(g(g(x0, x0), g(x0, x0)), g(g(x0, x0), g(x0, x0)))]. ==================================================================== 7. (4 points) Define a predicate divisors(number, list) which suceeds of 'list' is the list of the divisors of the natural number 'number'. If 'number' is not a natural number, the program should print an error message and fail. Sample runs: ?- divisors(1, Divisors). Divisors = [1]. ?- divisors(2, Divisors). Divisors = [1, 2]. ?- divisors(3, Divisors). Divisors = [1, 3]. ?- divisors(4, Divisors). Divisors = [1, 2, 4]. ?- divisors(9, Divisors). Divisors = [1, 3, 9]. ?- divisors(12, Divisors). Divisors = [1, 2, 3, 4, 6, 12]. ?- divisors(100, Divisors). Divisors = [1, 2, 4, 5, 10, 20, 25, 50, 100]. ?- divisors(101, Divisors). Divisors = [1, 101]. ?- divisors(10.1, Divisors). 10.1 is not a positive integer. false. ?- divisors(-101, Divisors). -101 is not a positive integer. false. ?- ?- divisors(30, X). X = [1, 2, 3, 5, 6, 10, 15, 30] Yes ================================================================== 8. (4 points) (a) Write a DCG that generates the language consisting of all the strings of length 5 built from the letters a, b, and c. Write also the Prolog program that corresponds to this DCG. (b) Write a DCG that generates the language consisting of all the strings of the form a^nb^n, n>0, i.e., the language consisting of the string ab, aabb, aaabbb, aaaabbbb,.... Write also the Prolog program that corresponds to this DCG. (c) Let a^n b^2n, n>=0 be the formal language which contains all strings of the following form: the empty string, abb, aabbbb, aaabbbbbb, ... Write a DCG that generates this language. Write also the Prolog program that corresponds to this DCG. (d) Write a DCG that defines a parametrised nonterminal star(X) such that, for any atom a, star(a) accepts the regular language consisting of all strings of the following form: the empty string, a, aa, aaa, aaaa, .... Write also the Prolog program that corresponds to this DCG.