----------Rimski 4isla: 

r(i,1).
f(x):-r(A,B),B=<X,not(r(D,E),E>B,E<=X),write(A),X1 is X-B,f(X1).

-------------Diferencirane:

d(c,1).
d(x,0):-number(x).
d(X+Y,DX+DY):-d(X,DX),d(Y,DY).
d(X*Y,DX*Y+DY*X):-d(X,DX),d(Y,DY).
d(sin(X),cos(X)*DX):-d(X,DX).

-------------Purvi element na spisak:

first(H,[H|T]).



---------------Posleden :

last(X,[X|[]]).
last(X,[H|T]):-last(X,T).

--------------Dali e list :

list([]).
list([H|T]).

--------------Memeber :

member(X,[X|T]).
member(X,[H|T]):-member(X,T).

--------------Obsht element :

oe(A,B):-member(X,A),member(X,B).

---------------Duljna :

length(0,[]).
length(N,[H|T]):-length(M,T),N is M+1.

--------------minimalen element


min(X,[X]).
min(X,[H|T]):-min(Y,T),m(X,H,Y).

===========minimalen ot dva :

m(H,H,Y):-H<Y.

m(Y,H,Y):-H>=Y.

--------------vtori na4in za min

min(X,L):-member(X,L),not(member(Y,L),X > Y).


append([],B,B).
append([H,T],B,[H|X]):-append(T,B,X).

--------------prefiks

preffix([],A).
prefiix([X],[X|T]).
preffix([X|T1],[X,T2]):-preffix(T1,T2).

-----------podspisak

sublist([],B).
sublist(A,[H|T]):-preffix(A,[H|T]),sublist(A,T).

-----------remove

remove(X,[H|T],T).
remove(X,[H|T],[H|L1]):-remove(X,T,L1).

----------reverse

reverse([],[]).
reverse([H|T],L):-reverse(T,L1),append(L1,[H],L).


------------sort

sort([],[]).
sort(L1,L2):-min(X,L1),remove(X,L1,L2),sort(L3,L4),L2 is [X|L4].

---------------permutacii

perm([],[]).
perm(L,[H|T]):-member(H,L),remove(H,L,L1),perm(L1,T).


----------------sortiran li e

issorted([]).
issorted([H|T]):-min(H,[H|T]),issorted(T).

issorted([]).
issorted([M]).
issorted([A,B|H]):-A<=B,issorted([B|H]).


--------------------sorted

sort(L,S):-perm(L,S),issorted(S).

----------------

perm(L,[H|T]):-set(L,S),member(H,S),remove(H,L,L1),perm(L1,T)

-----------------set(L,S).

removefirst(H,[H|T],T].
removefirst(H,[A|T],[A|T1]):-A\H,removefirst(H,T,T1).


-----dobavqne na element kum naredeno durvo:

add(x,[],[[],X,[]]).
add(X,[L,T,R],[L1,T,R]):-X<T,add(X,L,L1).
add(X,[L,T,R],[L,T,R1]):-X>=T , add(X,R,R1).




------durvo ot spiskuk

mt([],[]).
mt([H|T],Tree):-mt(T,T1),add(H,T1,Tree).

-----lqvo koren dqsno


ltr([],[]).
ltr([L,T,R],A):-ltr(L,SL),ltr(R,SR),append(SL,[T|SR],A).


-----sortirane 4rez dvoi4no durvo

tsort(L,S):mt(L,T),ltr(T,S).

-------razcepva spisuk

split([],X,[],[]).
split([H|T],X,[H|A],B):-H<X,split(T,X,A,B).
split([H|T],X,A,[H|B]):-H>=X,split(T,X,A,B).

--------quick sort

qsort([],[]).
qsort([H|T],Res):-split(T,H,L,R),qsort(L,LL),qsort(R,RR),append(LL,[H|RR],Res).


-----generira estestveni 4isla

u(0).
u(x):-u(N), x is N+1.

----suma na dve 4isla.

s(0).
s(x):- u(y),u(z), x is y*y + z*z.

----s interval

u(A,B,A).
u(A,B,X):-A<B,A1 is A+1,u(A1,B,X).
s(0).
s(x):-u(0,X,Y),u(0,X,Z),x is y*y + z*z.




--------------graffffffffff

arc(X,Y,G):-edges(G,E),memeber([X,Y],E).

arcs(X,G,L):-edges(G,E),filter(E,X,L).

filter([H,Y]|T,X,L):-filter(T,X,L1),append([[X,Y]],L1,L).
filter([[X,Y]|T),X,[Y|L1]):-filter(T,X,L1).
filter([[NOTX,Y]|T],X,L1):-X\=NOTX,filter(T,X,L1).

has-path(V1,V1,G,[]).
has-path(V1,V2,G,[[V1,Y]|P]):-arc(V1,Y,G),remove([V1,Y],G),has_path(Y,V2,G,P).

component(X,G,L):-verticies(G,V),sameComponent(X,V,G,L).

samecomponent(X,[],G,[]).
samecomponent(X,[H|T],G,[H|L]):-has-path(X,H,G,Path1), has-path(H,X,G,Path2),samecomponent(X,T,G,L).
samecomponent(X,[H|T],G,L):-samecomponent(X,T,G,L).


prim(G,V,[],[]).
prim(G,V,NV,,ST):-member(X,V),arc(X,Y,G),member(Y,NV),remove(Y,NV,NV2),prim(G,[Y|V],NV2,ST2),ST is [[X,Y]|ST2].


spanning_tree(G,G):-empty(G).
spanning_tree(G,ST):-verticies(G,[H|T],prim(G,[H],T,ST).

empty([[],[]]).


===============================avtomat====================


%finite state machine [Q,S,F,D]
%  Q - states
%  S - start states
%  F - final states
%  D - transitions

%simple state machine definitions
eps([[0],[0],[0],[]]).
letter(A,[[0,1],[0],[1],[[0,A,1]]]).

%increases labels of the machine states
r1([],N,[]).
r1([H|T],N,[H1|T1]):-H1 is H+N,r1(T,N,T1).
r2([],N,[]).
r2([[X,A,Y]|T],N,[[X1,A,Y1]|T1]):-X1 is X+N,Y1 is Y+N,r2(T,N,T1).
raise([Q,S,F,D],N,[Q1,S1,F1,D1]):-r1(Q,N,Q1),r1(S,N,S1),r1(F,N,F1),r2(D,N,D1).

%common list lib
length([],0).
length([H|T],N):-length(T,N1),N is N1+1.
append([],A,A).
append([H|T],A,[H|P]):-append(T,A,P).
member([H|T],H).
member([H|T],A):-member(T,A).

%unites two state machines
union([Q1,S1,F1,D1],Machine,[Q,S,F,D]):-
	length(Q1,N),
	raise(Machine,N,[Q2,S2,F2,D2]),
	append(Q1,Q2,Q),
	append(S1,S2,S),
	append(F1,F2,F),
	append(D1,D2,D).

%adds transition between pre-final states and the initial states of a state machine	
addToStart(State,A,[],[]).
addToStart(State,A,[S|T],[[State,A,S]|T1]):-addToStart(State,A,T,T1).
cat([],F1,S2,[]).
cat([[X,A,Y]|T],F1,S2,D):-member(F1,Y),addToStart(X,A,S2,L),cat(T,F1,S2,D2),append(L,D2,D).
cat([[X,A,Y]|T],F1,S2,D):-not(member(F1,Y)),cat(T,F1,S2,D).

%concatenates two state machines
concat([Q1,S1,F1,D1],Machine,[Q,S,F2,D]):-
	member(S1,X),member(F1,X),
	length(Q1,N),
	raise(Machine,N,[Q2,S2,F2,D2]),
	append(S1,S2,S),
	append(Q1,Q2,Q),
	cat(D1,F1,S2,ND),
	append(D1,D2,D3),
	append(D3,ND,D).
concat([Q1,S1,F1,D1],Machine,[Q,S1,F2,D]):-
	not(member(S1,X),member(F1,X)),
	length(Q1,N),
	raise(Machine,N,[Q2,S2,F2,D2]),	
	append(Q1,Q2,Q),
	cat(D1,F1,S2,ND),
	append(D1,D2,D3),
	append(D3,ND,D).

%defines A+ operation of state finite machine A
plus([Q,S,F,D1],[Q,S,F,D]):-cat(D1,F,S,ND),append(D1,ND,D).	

%defines A* operation of state finite machine A
star(A,B):-plus(A,A1),eps(E),union(A1,E,B).

%defines A? operation of state finite machine A
question(A,B):-eps(E),union(A,E,B).

%indicates whether a word passes a state finite machine
pass([],X,[Q,S,F,D]):-member(F,X).
pass([W|T],X,[Q,S,F,D]):-member(D,[X,W,Y]),pass(T,Y,[Q,S,F,D]).
match(W,[Q,S,F,D]):-member(S,S1),pass(W,S1,[Q,S,F,D]).

?-letter(a,A),letter(b,B),star(B,B1),concat(A,B1,AB1),concat(AB1,A,AB1A),match([a,a],AB1A).