首页 > 代码库 > 有确定性的有穷自动机

有确定性的有穷自动机

 

#include <stdio.h>  //s为初态,z为终态
int in(int s,int z)
{    
    if(s == z)  
    {        
        printf("3\nlook!the last status belongs to Z");   
        return 1;   
    }   
    else  
    {     
        return 0;   
    } 
} //s为状态,t为输入的字符
int step(int s,char t)
{ 
    if(t == a)   
        switch(s)  
    {             case 0:return 1; 
            case 1:return 3;
            case 2:return 1;    
            case 3:return 3;      
    }  
    else if(t == b) 
        switch(s)     
    {
             case 0:return 2;  
             case 1:return 2;  
             case 2:return 3;   
             case 3:return 3;    
    }
} 
int realize(char *input) 
{  
    int z = 3; 
    
    int s,i;   
    
    s = 0;  
    
    for(i=0;input[i]!=\n;i++)  
    {   
        printf("%2d",s);
        
        s = step(s,input[i]);     
    }   
    if(in(s,z))   
    {        
        return 1;  
    }       
    else      
    {         
        return 0;
        
    }
}  
main() { 
    int i;  
    int a;  
    char input[40]; 
    printf("FA=({0,1,2,3},{a,b},M,0,{3})\n");  
    printf("M:\n");
    printf("    M(0,a)=1    M(0,b)=2\n");
    printf("    M(1,a)=3    M(1,b)=2\n");  
    printf("    M(2,a)=1    M(2,b)=3\n");
    printf("    M(3,a)=3    M(3,b)=3\n");  
    printf("请输入你要检查的串");  
lop: 
    for(i=0;input[i-1] != \n;i++)  
    {
        scanf("%c",&input[i]);    
    }        
    for(i=0;input[i-1]!=\n;i++) 
    {          
        if(input[i] != a&&input[i] != b&&input[i] != \n)  
        {             
            printf("input error,enter again please:\n");
            goto lop;       
        }           
    }         printf("the status sequence is :\n");    
    a = realize(input);
    if(a == 1)  
        printf("\nSo this string can be identified\n");   
    else           
        printf("\nSo this string can‘t be identified\n");    
    printf("press enter to exit the program\n");  
    getchar();  
}

 

有确定性的有穷自动机