Implementation of DFA string recognition based on C language simulation

DFA Programming implementation of

One 、 Experiment task

Write a C Language program , Simulation Implementation DFA The process of identifying strings .

Two 、 Experimental content

DFA The input of ;
DFA Storage, read and write ;
DFA Check the correctness of ;
DFA The list of language sets displayed ;
DFA Rule string decision ;

3、 ... and 、 Content description

DFA The input of ：
Input separately DFA Of “ Character set ”、“ State set ”、“ Start state ”、“ Accept state set ”、“ State transition table ” The content such as , And save it in the set variable .

DFA Storage, read and write ：
Put the above DFA The five tuples of are saved in a text file , The extension is specified as .dfa. Please design by yourself DFA File storage format , And explain what it means . Can save in memory variables DFA write in DFA file , Also can be DFA File read into memory .（ reflection ： For sparse DFA（ There are many empty places in the conversion table ） Or use “ or ” Expressive transformational DFA（ The following test case 3 ）, How to improve DFA Expression of conversion table .）

DFA Check the correctness of ：

Check the uniqueness of the elements of all sets .
Check “ Start state ” Is it unique? , And whether it is included in “ State set ” in .
Check “ Accept state set ” Is it empty , And whether it is included in “ State set ” in .
Check “ State transition table ” Is it satisfactory? DFA The requirements of .
Check “ State transition table ” It's not whether it's handled properly when it's full .
DFA The list of language sets displayed ：
Enter the maximum length of the string to be displayed N, Output the above defined DFA The length of the language set ≤N All rule strings .（ Tips ： Notice in the algorithm while Number of cycles ）

DFA Rule string decision ：
Input （ Or use character set to generate randomly ） A string , simulation DFA The process of identifying a string determines whether the string is a regular string （ Belong to DFA Language set for ）.

Four 、 The test case

5、 ... and 、DFA Storage format recommendations

3 //  The number of characters in the character set  ( The following two lines can also be merged into one line )
/ * o //  Space delimited character set .O Represents any non / and * The characters of 
5 //  The number of States  ( The following two lines can also be merged into one line )
1 2 3 4 5 //  Status number . If the agreement is always used from 1 The consecutive numbers at the beginning indicate , Then this line can be omitted 
1 //  Number of start status . If the agreement is 1, Then this trip can save 
1 //  Number of end states . If the agreement is 1, Then this line can be omitted 
5 //  The number of the end state 
2  -1  -1 //  state 1 All outgoing conversions . Given in the order of characters in the character set .-1 Indicates the error status 
-1  3  -1
-1  4   3
5   4   3
-1  -1  -1

6、 ... and 、 Programming

• Characters to define 、 State, etc .

string inputChar;           // String to match 
string charracters;         // Character set 
int stateNum = 0;           // The number of States , The default is 0
int currState = 1;          // Start status number , The default is 1
int endNum = 1;             // Number of accepted States , The default is 1
int *acceptState = NULL;    // Acceptance state 
int **convertFrom = NULL;   // Conversion table 

from .dfa Read characters in the file 、 Status and transition criteria .
In reading this part, I didn't read directly from the file at the beginning , Because I don't know how to read data from the file , So I input the data manually after writing , At the beginning, there was bug You can also know what's wrong in the program , As a result, I adjusted and repaired some bug Then it can operate normally , After the manual test , I just joined the data input from the file read function , Then learn how to read data from files .

void init();		// Manual input 
void read();		// from .dfa The data is read from the file 

• To recognize the input of a string .

void input()
{
    cout << " Enter the string to recognize " << endl;
    cin >> inputChar;
}

DFA The identification of . This dfa The idea of matching is
According to the state transition table , Judge whether it can switch from the current state to the next state according to the input characters , If it doesn't , It means that the match is not successful , The input string is not dfa The state set of .
If you match the complete input string , Judge whether the current state is in the given acceptance state , If you are , Note that the input string is a string that can be matched , No, it's not .

void DFA()
{
    int num = 0;
    while (num < (int)inputChar.length())
    { // Loop matches the input characters 
        int y = 0;
        bool isExist = false; // Detect whether the next character is in the character set 
        for (; y < (int)charracters.length(); y++)
        {
            if (inputChar[num] == charracters[y])
            {
                isExist = true;
                break;
            }
            // Any character match 
            else if (y == charracters.length() - 1 && charracters[y] == '?')
            {
                isExist = true;
                break;
            }
        }
        if (isExist)
        { // Check whether the input characters can match in the current state transition table 
            if (convertFrom[currState - 1][y] > 0)
            {
                currState = convertFrom[currState - 1][y];
            }
            else
            {
                cout << " Current character matching error  -1 :" << num + 1 << " " << inputChar[y] << endl;
                return;
            }
        }
        else
        {
            cout << " The current character cannot be faulted , There is no character set :" << num + 1 << " " << inputChar[y] << endl;
            return;
        }
        num++;
    }
    bool notAcceptState = true; // Judge whether the current status is in the debit status 
    for (int i = 0; i < endNum; i++)
    {
        if (currState == acceptState[i])
        {
            cout << " The match is successful " << endl;
            notAcceptState = false;
        }
    }
    if (notAcceptState)
    {
        cout << " The string is not in the accepted state " << endl;
    }
}

DFA The list of language sets displayed . In this part, I use recursion to output the above defined DFA The length of the language set ≤N All rule strings .
The specific idea is to search the characters in the conversion table that can be matched by the current state through depth first . When a character that can change state is matched , Record this character in an array under the column of the conversion table , This is used for output when matching to a string in the language set later .
At every recursion , It will judge whether the currently matched character length has exceeded the specified length N, Then judge whether the current state is in the acceptance state , If yes , You can output the matched characters . Note that the character length is N Cannot continue recursion .

void outChars(int n, int *arr);	// Output function 
void isAcceptState(int currstate, int n, int *arr);	// Check function 
void searchChars(int currstate, int n, int N, int *arr){
    if (n < N) { // Match one character at a time , Judge whether the matched string is dfa Language set     
        isAcceptState(currstate, n, arr);
    }
    else{
        isAcceptState(currstate, n, arr);
        return;
    }
    for (int i = 0; i < (int)charracters.length(); i++){
       // From the start state, match the characters that can go out in turn according to the conversion table and convert the state through recursive traversal 
        if (convertFrom[currstate - 1][i] > 0) {
            arr[n] = i;
            n++;
            searchChars(convertFrom[currstate - 1][i], n, N, arr);
            n--;
        }
    }
}

7、 ... and 、 Experimental tests

• Input dfa In file

   first line   Is a character set 
   The second line   Is the number of States , The default is from state 1 Start , So there is no need to enter the start state 
   The third line   Accept the number of states for the behavior 
   In the fourth row   In the accepted state 
   The fifth row   Start as state transition table . List as character set , It corresponds to a two-dimensional array , In which state, enter which character and go to which state ,-1 Is in the error state .

• DFA(1) Of DFA file

ab
4
1
4
2 3
4 3
2 4
4 4

• Compile run program
  DFA(1)

 Manual input ：1 , Read from file  0
0
 Enter the string to recognize 
aabb
 The match is successful 
 Enter the maximum length of the string to be displayed N
5
aa
aaa
aaaa
aaaaa
aaaab
aaab
aaaba
aaabb
aab
aaba
aabaa
aabab
aabb
aabba
aabbb
abaa
abaaa
abaab
ababb
abb
abba
abbaa
abbab
abbb
abbba
abbbb
baa
baaa
baaaa
baaab
baab
baaba
baabb
babaa
babb
babba
babbb
bb
bba
bbaa
bbaaa
bbaab
bbab
bbaba
bbabb
bbb
bbba
bbbaa
bbbab
bbbb
bbbba
bbbbb

The other two DFA Don't list the results , To test the other two DFA It just needs to be modified read() Function input file is good , The code file will be shown later .

Besides , There is no guarantee that anything else DFA Can pass. , Because there are only these three test files , Limited cases . And this one. DFA Did not meet all the requirements of the experiment , So please pay attention to what you want to refer to .