I._______________________________________
Definer et predikat
	stav(T,B)
som holder dersom T er en liste med siffre og B er en liste med tilsvarende
siffernavn. (Tenk paa det som en oversetter som tar som input et tall skrevet
i desimal notasjon og gir et tilsvarende tall der hvert siffer er skrevet med
ord.) F.eks.
      stav([1,3,5,2],[en,tre,fem,to]).



II._______________________________________
Definer et predikat
	pivoting(P,L,L1,L2)
der L er en liste med heltall og L1 er listen med alle elementer fra L som
er =<P mens L2 med alle som er >P.

Definer saa et predikat
	quick_sort(L,R)
som holder naar R er sortert L, der sortering skjer som i quicksort
algoritme. 

[NB! 'append' er en tidskostbar operasjon saa proev aa unngaa den!]



III._______________________________________
Gitt en representasjon av en graf som en samling av (rettede) kanter p(a,b),
definer et predikat 
	apath(Start,Slutt,Sti)
som holder kun naar Sti er en liste med en asyklisk sti fra noden Start til
Slutt.
 
[NB! Soerg for at predikatet terminerer i alle tilfeller ved aa bruke
negasjon pa en passende maate. Du kan ogsaa faa bruk for en ekstra
akkumulatorvariabel som holder rede paa stien konstruert "saa langt".] 



IV._______________________________________
Design a parser in Prolog for the following CFG:

     S ::= NP VP
    VP ::= VI | VT NP
    NP ::= hospital | nurses | doctors | ....
    VI ::= walks | jumps | ...
     V ::= employs | ...


Lexical analysis in Prolog would be extremely cumbersome, due to Prolog's
poor I/O facilities. We will therefore ignore this aspect completely and
consider only parsing with lists of lexical tokens as input/output (i.e.,
lists like [hospital, employes, nurses], etc.) 

a._______________________________________________________

The difference list technique allows us to make the Prolog code close to
isomorphic to the rules of the grammar whose language is recognized.

% A simple top-down recognizer
%
% illustrating also use of DIFFERENCE LISTS
% to avoid explicit concatenation
%
% rules
s(X-Z)   :- np(X-Y), vp(Y-Z).
vp(X-Z)  :- vi(X-Z).
vp(X-Z)  :- vt(X-Y), np(Y-Z).
%
% lexicon
%
np([hospital|X]-X).
np([doctors|X]-X).
np([nurses|X]-X).
np([patients|X]-X).
vi([walks|X]-X).
vi([jumps|X]-X).
vt([employs|X]-X).
%

The first rule here can be paraphrased as saying that we can find an S at the
start of X (with Z the portion of string left behind after it)) if we can
find an NP at the beginning of X, leaving Y behind, and a VP at the beginning
of Y, with Z left behind after that. 

We can use this very same code to do generation as well as recognition. Try the following:

   ?- s(Sentence-[]).


b.________________________________________________________

It is straightforward to convert the recognizer into a parser (which
generates (abstract) syntax trees) for the input sequences,  simply by the
addition of extra arguments. Each predicate in the program, which captures
the notion of a particular grammatical category, is provided with an extra
argument (appearing as the first argument, say) which describes (as a list)
the structure of the phrase. In the logic translation of each
phrase-structure rule the tree corresponding to the LHS category will be
simply a list consisting of the category name followed by the trees of the
RHS categories. For example, the first rule can be extended as follows

      s([s,NP,VP],X-Z) :- np(NP,X-Y), vp(VP,Y-Z).

while one of the lexical rules:

      np([np,hospital],[hospital|X]-X).

We expect to obtain something like

    ?-  s( X, [hospital, employs, nurses|[]]-[] ).

    X = [s, [np,hospital], [vp, [vt,employs], [np,nurses]]]

c.________________________________________________________

Complete the extension of the recognizer to obtain a complete parser for our
language. 




V._______________________________________
Vi definerer en serie med ordpar som kan "byttes om", f.eks.
   bytt( jeg, du ).
   bytt( tysk, norsk ).
   bytt( maskin, tysk ). 
   bytt( maskin, menneske ).
   bytt( er, er-ikke ). 
   bytt( X, X ).
 etc.
Definer saa et predikat 
	endre(L,R)
som vil tillatte deg aa endre en setning L
(representert som en liste med ord) til en setning R ved aa benytte slike ordpar.
F.eks. med bytt definert som over, vil query:
   endre([jeg, er, maskin], X)
produsere:
   X = [du, er-ikke, norsk] ;
   X = [du, er-ikke, menneske] ;
   X = [du, er-ikke, maskin] ;
   ...