method.java

简化DFA-对于一确定型自动机M=(K,Σ,Δ,s, F)

public class method {
	private String da[][],fin,equal[],finalstring[],equalstates[];
	private int S,c,DA[][],count,k;
	protected String out[];
	public method(int S,int c,String a[][],String fin)
	{
		this.S=S;
		this.c=c;
		da=a;
		this.fin=fin;
		count=1;k=1;
		out=new String[50];
		equal=new String[c+1];
		equalstates=new String[S];
		DA=new int[S][S];
		String s[]=fin.split(" \\s*");
		finalstring=s;
		equal[c]=fin;		
		mainmethod();
	}
    public String andstate(String f)
    {  	
    	if(f.compareTo("")!=0)
    	{
    	    String array[]=f.split(" \\s*");
    	    String arrayout=array[0];
    	    for(int i=1;i<array.length;i++)
    		{    
    		    for(int j=0;j<i;j++)
    		   {
    		    	if(array[i].compareTo(array[j])==0) break;
    		    	if(j<i-1) continue;
    		    	else arrayout+=" "+array[i];
    		   }
    		}
    	    return arrayout;
    	}
    	else return f;
    }
	public int find(String s)
	{
    	int i;
		for(i=0;i<S;i++)
    	    if(da[i][0].compareTo(s)==0) break;
    	return i;
	}
	public boolean isfinal(String s)
    {
    	int i;
    	for(i=0;i<finalstring.length;i++)
    		if(Integer.parseInt(finalstring[i])==find(s)) return true;
    	return false;
    }
    public void equals()
    {
    	for(int j=1;j<c;j++)   
    	{
    		equal[j]="";
    		for(int i=0;i<S;i++)
    			if(isfinal(da[i][j])&&!isfinal(da[i][0])) equal[j]+=i+" ";	
    	}
    }
    public void findnotused()
    {
    	equals();
    	String s="";
    	for(int i=1;i<c+1;i++)
    		s+=equal[i];
    	equal[0]=notused(s);
    }
    public String notused(String s)
    {
    	String Notuse="";
    	String notuse[]=s.split(" \\s*");
    	for(int i=0;i<S;i++)
    	{
    		for(int j=0;j<notuse.length;j++)
    		{    		
    			if(Integer.parseInt(notuse[j])==i) break;
    			if(Integer.parseInt(notuse[j])!=i&&j>=notuse.length-1) 
    			   Notuse+=i+""+" ";
    		}
    	}
    	return Notuse;    	
    }
    public String Notused(String s)
    {
    	String Notuse="";
    	String notuse[]=s.split(" \\s*");
    	for(int i=0;i<S;i++)
    	{
    		if(!isfinal(da[i][0]))
    		{
    			for(int j=0;j<notuse.length;j++)
    		   {    		
    			   if(notuse[j].equals(da[i][0])) break;
    			   if(notuse[j].compareTo(da[i][0])!=0&&j>=notuse.length-1) 
    			       Notuse+=da[i][0]+" ";
    		    }
    		}
    	}
    	return Notuse;    	
    }
	public void foundform()
	{
		findnotused();
		for(int i=0;i<c+1;i++)
		{
			if(equal[i].compareTo("")!=0)
			{
				String s[]=equal[i].split(" \\s*");
			    for(int j=0;j<s.length;j++)
				    for(int k=j+1;k<s.length;k++)
				   {   
					  int n=Integer.parseInt(s[j]);
					  int m=S-1-Integer.parseInt(s[k]);
					  DA[n][m]=1;
				   }
			}
		}
	}
	public void form()
	{
		foundform();
		for(int i=0;i<S;i++)
			for(int j=0;j<S;j++)
				if(DA[i][j]!=1)  DA[i][j]=0;
	}
    public void equalstate() 
    {
    	form();
    	boolean enable=false;
    	while(!enable)
    	{
    		enable=true;
    		for(int i=0;i<S-1;i++)
    			for(int j=0;j<S-i-1;j++)
    				if(DA[i][j]==1)
    				{
    					for(int k=1;k<c;k++)
    					{
    						if(find(da[i][k])==find(da[S-j-1][k])) continue;
    						else if(find(da[i][k])==(S-1)||find(da[S-j-1][k])==0)
    						     {
    							     if(DA[find(da[S-j-1][k])][S-find(da[i][k])-1]==0)
    					             {
    							         DA[i][j]=0;System.out.println("23");
    					                 enable=false;
    				                  }
    						         else continue;
    						     }
    							  else
    							  {
    								  if(DA[find(da[i][k])][S-find(da[S-j-1][k])-1]==0)
     					              {
     							         DA[i][j]=0;System.out.println("23");
     					                 enable=false;
     				                  }
     						          else continue;
    							  }
    					}
    				}
    	}
    }
    public boolean judge(int k,int y)
    {
    	for(int i=0;i<S-k-1;i++)
    		if(DA[i][k]==1&&i!=y) return false;
    	return true;
    }
    public void findequal()
    {
    	equalstate();
    	for(int i=0;i<S-1;i++)
		{
    		boolean jud=true;
    		for(int j=0;j<S-i-1;j++)
				if(DA[i][j]==1&&((i==0)||judge(j,i))) 
				{
					equalstates[count]="";
					equalstates[count]+=da[i][0]+" "+da[S-j-1][0]+" ";
    		        jud=false;
				}		    
    		
    		if(!jud)  
    		{
    			equalstates[count]=andstate(equalstates[count]);
    			count++;  		
    		}
		}
    	equalstates[0]="";equalstates[count]="";
    	for(int i=1;i<S;i++)
    		equalstates[0]+=equalstates[i]+" ";
    	equalstates[0]=Notused(equalstates[0]);
		for(int i=0;i<finalstring.length;i++)
			equalstates[count]+=da[Integer.parseInt(finalstring[i])][0]+" ";
		changeform();
    }
    public int whichequal(String s)
    {
    	int i;
    	for(i=0;i<S;i++)
    	{
    		if(equalstates[i].compareTo("")!=0)
    		{
    			String states[]=equalstates[i].split(" \\s*");
    		    for(int j=0;j<states.length;j++)
    			    if(s.compareTo(states[j])==0) return i;
    		}
    		
    	}
    	return i;
    }
    public void changeform()
    {
    	for(int i=0;i<S;i++)
    		for(int j=0;j<c;j++)
    			da[i][j]=equalstates[whichequal(da[i][j])];
    }
    public boolean sort(String s)
    { 
    	  for(int i=0;i<count;i=i+c)
		 {
		     if(s.compareTo(out[i])==0) break;
		     if(s.compareTo(out[i])!=0&&i+c>=count) return true;	  
		 }
		 return false;		
    }
    public void mainmethod()
    {	
    	findequal();
    	out[0]=da[0][0];
    	for(int i=1;i<c;i++)
    		out[i]=da[0][i];
    	count=1;
        count+=c-1;
    	while(k<count)
    	{   
    		if(k%c!=0&&out[k].compareTo("")!=0)
    		{
    		    if(sort(out[k]))
    		   {
    		       out[count]=out[k];
    		       for(int q=1;q<c;q++)
    				  out[count+q]=da[find(out[k])][q];
    			   count+=c;
    		   }
    		}
    		k++;
    	}
    }
	public int getcount()
	{
		return count/c;
	}
}