NFA determination and DFA minimization based on C language

NFA Deterministic sum DFA To minimize the

One 、 Experiment task

1. Storage NFA And DFA;
2. Programming the subset construction method will NFA convert to DFA.
3. Perfect first DFA, And minimize it DFA.

Two 、 Experimental content

determine NFA And DFA The storage format of . Requirements for 3 More than tests NFA Prepare the storage files of the corresponding finite automata .
use C or Java Language writing will NFA convert to DFA The procedure of subset construction method of .
Get ready 3 More than tests DFA file .（ Tips ： There must be no minimization DFA）
DFA Manual improvement .（ If the state transition mapping is full ）
use C or Java The language is written by equivalent partition method to minimize DFA The program .
In fact, this part of the content is not so simple , And verify whether the conversion is successful , How to verify ？ As long as you find the original and modified subset （ If the length is less than a N）, Confirm that the two language sets are exactly the same . But I forgot this at the beginning , Later, when I checked and accepted, I found that it was not written , So I won't add this part .￣ω￣=

3、 ... and 、 Storage format

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

This part will not be copied , Input later will modify . But the format is roughly the same .

Four 、 Programming

Realize the idea
Think about writing a little , Otherwise, I feel something wrong .

nfa and dfa I've seen it for a long time , As long as the subset construction method is used for conversion . As for the subset construction method , Let's check it by ourselves , What I want to say is to pay attention to the arrival processing of empty characters , Circulation needs attention .
and dfa Minimization is the simplest , Anyway, I'm first divided into the set of acceptance States and the set of non acceptance States , Then divide the same transition state into one state . Of course , To modify the state transition .

The document states ：

  1. intArr.h intArr.cpp  Array class , Used to realize the union of digital sets , Delete , lookup 
  2. NFA_To_DFA.h NFA_To_DFA.cpp dfa turn nfa Class 
  3. minimalDFA.h minimalDFA.cpp  To minimize the dfa Class 
  4. main.cpp  The main function 

• Class design description

1）intArr class

class intarr
{
public:
    intarr();
    intarr(intarr &arr1);                   // copy constructor 
    int inline getSize(){return size;}      // Get the collection size 
    void cleanArr();                        // Empty set elements 
    void operator &= (int num);             // heavy load &=, Incorporate a single element 
    void operator &= (intarr &arr1);        // heavy load &=, Merge into a collection 
    void getSort();                         // Sort the set elements from small to large 
    int &operator[](int i);                 // heavy load [], You can get elements like arrays 
    bool operator == (intarr &arr1);        // heavy load ==, Determine whether two sets are equal 
    bool getNum(int num);                   // Determine whether a number is in the set 
    void delNum(int num);                   // Delete a number 
    int getNumber();                        // Get the number of created objects 

private:
    int *arr=NULL;      // Array pointer 
    int size;           // Array size 
    static int number;  // Number of objects created 
};

2） NFA_To_DFA class

dfa Medium dfa aggregate

struct state
{
    int stateNum;        // The number of this status 
    int *nextNum;        // According to which state the input character will point 
    intarr nfaArr;       //NFA State set 
    bool isMake = false; // Whether to mark 
    static int maxNum;   // Maximum status label 
};

Shared one dfa state , As an intermediate state for creating new dfa state

struct sstate
{
    intarr nfaArr; //NFA State set 
    int stateNum = 0;
};

nfa turn dfa Class

class nfa_to_dfa
{
  public:
    nfa_to_dfa(std::string fn); // Default constructor 
    void getIntArr(int num, std::string s);
    void closure_s();                     // Null character matching 
    void closure_T(int num, int charNum); // Character set matching 
    void inStates();                      // Is it in the current DFA In status 
    void read();                          // Read NFA data 
    void convert();                       // Start conversion 
    void output();
    ~nfa_to_dfa() {} // Destructor 

  private:
    std::string charracters;          //nfa Character set 
    int charrLength = 0;              // Length of character set 
    int statesNumber = 0;             //nfa The number of States , The default is 0
    int currState = 1;                // Start status number , The default is 1, No input 
    int endNum = 1;                   //nfa Number of accepted States , The default is 1
    int *acceptStates = NULL;         //nfa Accept state set 
    std::string **convertFrom = NULL; // Conversion table 
    std::string filePath;             // File input object 
    sstate shareState;                // A shared object , Used to convert 

    int acceptNum = 0;      // Converted dfa Number of accepted States 
    intarr DfaAcceptstates; //dfa Accept state set 
};

3）minimalDFA class

To minimize the dfa A state of , Describe with structure

struct minState
{
    static int maxNum;      // Maximum number of States 
    intarr sameState;       // The state set of the same output 
    int  minNum;            // This is the smallest dfa Status mark of 
    int *nextState=NULL;    // In the case of different input characters, it points to a set of different states 
    int isAcceptState=0;    // Whether it is accepted 
};

To minimize the dfa. Algorithmic thought ：
First, the state is divided into accepted state and non accepted state . about dfa When inputting the same characters to the same state, these states are divided into a group .

class minDfa
{
  public:
    minDfa(std::string str);  // Constructors 
    void read();              // Reading data 
    void divide();            // Divide dfa
    void output();            // State set 
    bool isqueal();           // Judge two minimization dfa Whether it is equal or not 

  private:
    std::string charracters;  // Character set 
    int charLength=0;
    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 
    minState *states;         // To minimize the dfa State set 
    std::string path;         // The way to read the file 
};

5、 ... and 、 Experimental tests

• Input nfa In file

  first line   Is a character set  ,? For empty characters 
  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 .

• NFA Convert to DFA

1）nfa_to_dfa The input file of nd：(aa|b)(a|bb)

ab?
4
1
3
2,1,3,
1,-1,-1,
3,4,-1,
-1,3,-1,

2） In the file dfa_to_nfa Medium output :

ab
5
4
1 2 3 5 
{1,3,}		2 3 
{2,3,}		1 4 
{1,3,4,}		2 3 
{4,}		-1 5 
{3,}		5 4 

3） As minDfa The input file of dfa：

ab
5
4
1 2 3 5 
2 3 
1 4 
2 3 
-1 5 
5 4 

4） To minimize the mindfa Output

{1,3,}	1: 2 1 		isacceptstate:1
{2,}	2: 1 3 		isacceptstate:1
{4,}	3: -1 4 		isacceptstate:0
{5,}	4: 4 3 		isacceptstate:1
***********