.pro, if you wish to avoid confusion with Perl files) as the extension for the source files.)
*.testcreated by using the Unix
scriptcommand to test all of your predicates. Use the command
lprto print the Prolog *.test files. Make sure the
ExerciseN.testfile when printed can be understood. Here's an example of how to use
script ExerciseN.test pl -g truethis option suppresses the startup message . . do tests . . .
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
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.
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
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
transformed(Term, Variable, Result)computes or tests a
Resultterm which is algebraically equal to the
Term, but is of the form
. For example,
transformed(-5, z, -5*z**0)should succeed.
transformedTerms(Polynomial, Variable, Result)computes a list of the terms in
Polynomialwith 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
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)
next_statepredicate for a FSA given on p. 175 to a list of transition triples with the form
[CurrentState, InputSymbol, NextState].
automatonwhich 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
automaton(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 ])
scanpredicates so that
fashas as arguments the name of an automaton and an input sequence, and
scanhas 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.
empty(A)which determines whether the language accepted by automaton
Ais the empty set.
Hint: the language is empty if no final state is reachable from the initial state.
disjoint(FSA1, FSA2)which tests whether the languages accepted by the automata FSA1 and FSA2 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 FSA1 and FSA2 are disjoint if their intersection is empty; it is straightforward to define an automaton A such that L(A) = L(FSA1) intersect L(FSA2).
finite(A)which tests whether the language accepted by the automaton
Ais infinite (look for a loop in the state-table.)