%DeterminiserVI
%*Can* supply a list of forbidden word indexes.
%If the string generated by appending a symbol to a string in a state is on
%the forbidden word index list there will be NO splitting.
function DeterminisedStates = DeterminiserVI(Sigma, L_Max, AlphabetLength, increment, DFName)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Determinisation Log Preliminaries
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
DLogFileName = strcat(DFName,'_DeterminisationLog.txt');
fid = fopen(DLogFileName,'w');
fprintf(fid,'%s \n \n','Determinisation Log');
%the states now
fprintf(fid, '\n');
for i= 1:size(Sigma,1);
fprintf(fid, 'State %s: ', num2str(i-1));
for j = 1:length(Sigma(i,:))
if Sigma(i,j) ~= 0
if j == 1
strings = dec2base(Sigma(i,j), AlphabetLength);
strings = strings(2:length(strings));
fprintf(fid, '%s', strings);
else
strings = dec2base(Sigma(i,j), AlphabetLength);
strings = strings(2:length(strings));
fprintf(fid, ', %s', strings);
end
end
end
fprintf(fid, '\n');
end
fprintf(fid, '%s \n',...
'______________________________________________________________________');
fprintf(fid, '\n');
fclose(fid);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Main Loop
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
NumStates = size(Sigma,1);
SizeStates = zeros(NumStates+1,1);
%find minimum index such that the word is of maximum length
allzeros = '1';
for i = 1:L_Max
allzeros = strcat(allzeros,'0');
end
MININDEX = base2dec(allzeros,AlphabetLength);
deterministic = 0;
while deterministic == 0
deterministic = 1;
NumStates = size(Sigma,1);
SizeStates(NumStates+1) = 0;
for S = 1:NumStates
%This function checks whether there are only strings of maximum
%length in this state. If there are then we are forced to make the
%approximation of using the maximum length strings to check the
%determinism (an approximation since they must be truncated)
Truncatable = CheckState(S,Sigma, L_Max, AlphabetLength, MININDEX);
Index = Sigma(S,1);
%Need to check whether the first string in the state is of maximum
%length or not. if it isn't or {it is and the state is truncatable} then
%continue. Else move on to the next string in the state and
%increment the position at which to start checking the rest of the
%state for determinism
%if we have a long string
if Index >= MININDEX
%if there is a short string we need to find
if Truncatable == 0
%find the first short string
i = 2;
while Index >= MININDEX
Index = Sigma(S,i);
i = i + 1;
end
StartPoint = i;
end
else
StartPoint = 2;
end
String = dec2base(Index,AlphabetLength);
FirstStringDestinations = zeros(AlphabetLength,1);
%Find destinations of the first string on appending each symbol
for j = 0:increment:AlphabetLength-1
NewString = strcat(String,num2str(j));
if length(NewString)>L_Max+1
NewString = strcat('1',NewString(3:L_Max+2));
end
to = base2dec(NewString,AlphabetLength);
Location = find(Sigma == to);
if isempty(Location) ~= 1
state = mod(Location, size(Sigma,1));
if state == 0
state = size(Sigma,1);
end
FirstStringDestinations(j+1) = state;
end
end
for x = StartPoint:size(Sigma,2)
Index = Sigma(S,x);
if Index ~= 0
String = dec2base(Index,AlphabetLength);
Destinations = zeros(AlphabetLength,1);
%Find destinations of the string on appending each symbol
for j = 0:increment:AlphabetLength-1
NewString = strcat(String,num2str(j));
LongString = 0;
if length(NewString)>L_Max+1
NewString = strcat('1',NewString(3:L_Max+2));
LongString = 1;
end
to = base2dec(NewString,AlphabetLength);
Location = find(Sigma == to);
if isempty(Location) ~= 1
state = mod(Location, size(Sigma,1));
if state == 0
state = size(Sigma,1);
end
Destinations(j+1) = state;
end
end
%Check to see whether destinations are the same
Difference = FirstStringDestinations-Destinations;
Difference = Difference.^2;
Difference = sum(Difference);
if Difference ~= 0
Same = 0;
else
Same = 1;
end
if Same ~= 1%if the destinations are not the same
%Don't take action if the word is long and the state is
%not truncatable
if LongString == 0 || LongString+Truncatable > 1
%add the offending string to a new state
Sigma(NumStates +1,SizeStates(NumStates+1)+1)=Index;
SizeStates(NumStates + 1) = SizeStates(NumStates + 1) + 1;
Sigma(S,x) = 0; %remove offending string from old state
deterministic = 0;
WriteDeterminisationLog(Index, FirstStringDestinations, Destinations,...
Sigma, AlphabetLength, DLogFileName);
end
end
end
end
%Don't look at the rest of the states if you've moved a string
if deterministic == 0
break
end
end
end
%Sigma could now have zeros scattered through it, so rewrite Sigma to
%DeterminisedStates shifting non-zeroes along
DeterminisedStates = zeros(size(Sigma));
for i = 1:size(Sigma,1)
count = 1;
for j = 1:size(Sigma,2)
if Sigma(i,j) ~= 0
DeterminisedStates(i,count) = Sigma(i,j);
count = count + 1;
end
end
end