- The first page of the report is a standard cover page.
- The body part of the report is a hardcopy of your answers in exercise order. For
each exercise for which you develop Prolog predicates you submit the following:
- A printout of your
**documented**predicates.**You must use**the command enscript to print the Prolog source file. You can use`.pl`

(or`.pro`

, if you wish to avoid confusion with Perl files) as the extension for the source files.) - A printout of the output files
`*.test`

created by using the Unix`script`

command to test**all**of your predicates. Use the command`lpr`

to print the Prolog *.test files. Make sure the`Exercise`

file when printed can be understood. Here's an example of how to use*N*.test`script`

:`script Exercise`

*N*.test pl -g true*this option suppresses the startup message*. .*do tests*. . .`<ctrl-D> exit`

While you can develop your predicates on your personal computer, be sure your file will load correctly and all your functions execute properly on Prism. You can submit the report to your instructor in class or to the assignment boxes accessible outside the main Computer Science office.`submit 3401 r3 report3`

### Question 1: solve a puzzle

The police are trying to track down the gang of three kids who have been stealing pumpkins. So far, they have established the following facts: the kids' first names are Angela, Mary, and David; one is 5, one is 7, and one is 8; one has the last name Diamond, and the one with the last name Grant is 3 years older than the one with the last name Leung. You can assume Angela and Mary are female and David is male.

Use the technique shown in the

`zebra`

example (`/cs/course/3401/zebra.pl`

) to find missing information on the gang: each child's age, gender, first name and last name, consistent with the data above. (Encode the above data as is -- do not add additional facts.)Use your Prolog code to show whether or not the computed information uniquely identifies the culprits.

### Question 2: polynomial terms in normal form

This exercise involves transforming a polynomial into a list of terms in normal form.

We assume a polynomial is given as a sum and/or difference of

- terms, each of which is either
- a coefficient or
- a variable raised to a power or
- a coefficient
*****a variable raised to a power.

- A coefficient is a constant expression.
- A constant expression is
- a numerical constant or
- a symbolic constant or
- an algebraic expression involving no variables.

- A variable raised to a power is
- a variable or
- a variable
******non-negative integer.

Expressions are parenthesized if necessary, following the usual rules for operator precedence (* has higher precedence than +, etc.)

The same power may occur in two different terms and there's no restriction on the order of the terms. Here are three examples of polynomials in the variable x which illustrate all the cases above:

`2 -100 + x*a - 2*x**7 x**3 - (a+b) - 0.5 * x**3 + x`

The examples above show that, in the usual mathematical notation, polynomials don't have a completely regular structure -- some terms have an exponent; some include a variable, some don't, etc. But programs which do symbolic algebra typically operate on algebraic expressions expressed in a

*normal form*with a uniform structure, in order to simplify the calculations. This exercise asks you to define and demonstrate Prolog predicates to transform a polynomial into a normal form in which- each term in the polynomial sum has a
*coefficient*,*variable*and a non-negative integer*exponent*, with the coefficient preceding the variable; - the polynomial itself is presented not as a sum or difference but as a
*list*of terms which are understood to be summed. - the terms are listed in descending order by exponent,
- terms with the same exponent are regrouped into a single term in the normal form.

`transformed/3`

and`transformedTerms/3`

as follows:`transformed(Term, Variable, Result)`

computes or tests a`Result`

term which is algebraically equal to the`Term`

, but is of the form`Coefficient*Variable**Power`

`transformed(-5, z, -5*z**0)`

should succeed.-
`transformedTerms(Polynomial, Variable, Result)`

computes a list of the terms in`Polynomial`

with each term transformed into normal form. As an example,`transformTerms(-100 + x*a - 2*x**7, x, [-2*x**7, a*x**1, -100*x**0])`

Most of the work will go into the

`transformed`

predicate. In order to get a better feel for declarative programming, avoid introducing unnecessary variables into the clauses. For example,

is much better than the equivalent`transformed(-Var, Var, (-1)*Var**1).`

`transformed(Term, Var, Result) :- Term = -Var, Result = (-1)*Var**1.`

You may wish to reduce your programming by using built-in predicates - for example,

`sort/2`

. To learn about built-in predicates and the SWI-Prolog library, you can download the SWI reference manual available at*http://www.swi-prolog.org*. You can also get some information from the`help/1`

and`apropos/1`

predicates in SWI-Prolog. For example,?- apropos(sort). sort/2 Sort elements in a list msort/2 Sort, do not remove duplicates keysort/2 Sort, using a key predsort/3 Sort, using a predicate to determine the order merge/3 Merge two sorted lists merge_set/3 Merge two sorted sets Yes ?- help(sort/2). sort(+List, -Sorted) Succeeds if Sorted can be unified with a list holding the elements of List, sorted to the standard order of terms (see section 4.6). Duplicates are removed. The implementation is in C, using natural merge sort (END)

### Question 3: FSA decision problems

This exercise builds on the discussion of finite-state automata in Ch. 21 of the text.- Change the
`next_state`

predicate for a FSA given on p. 175 to a list of transition triples with the form`[CurrentState, InputSymbol, NextState]`

. - In order to have several automata defined at the same time, let's give automata names. We can define a predicate
`automaton`

which relates a name to an automaton structure as a term:`automaton(`

.*name*, [*initialState*,*listOfFinalStates*,*transitionList*])For example, the automaton described on page 175 of the text could be represented by asserting

Rewrite theautomaton(evenXoddY, [ee, [eo], [ ee-x-oe, ee-y-eo, oe-x-ee, oe-y-oo, oo-x-eo, oo-y-oe, eo-x-oo, eo-y-ee ])

`fas`

and`scan`

predicates so that`fas`

has as arguments the name of an automaton and an input sequence, and`scan`

has three arguments: automaton name, input sequence, and current state.Demonstrate your automaton predicate by defining an automaton called

`nice`

with the structure of the Wikipedia example "Fsm parsing word nice". and showing what it does. - Implement and demonstrate a Prolog predicate
`empty(A)`

which determines whether the language accepted by automaton`A`

is the empty set.Hint: the language is empty if no final state is reachable from the initial state.

- Implement and demonstrate an algorithm in the form of a Prolog predicate
`disjoint(FSA1, FSA2)`

which tests whether the languages accepted by the automata FSA_{1}and FSA_{2}are disjoint, i. e., there is no input sequence which causes both FSAs to enter one of their final states.Hint: the languages accepted by FSA

_{1}and FSA_{2}are disjoint if their intersection is empty; it is straightforward to define an automaton A such that L(A) = L(FSA_{1}) intersect L(FSA_{2}). - Implement and demonstrate an algorithm in the form of a Prolog predicate
`finite(A)`

which tests whether the language accepted by the automaton`A`

is infinite (look for a loop in the state-table.)

**Last Updated:***November 6, 2005* - A printout of your