Experiment name
Convert any given NFA to a DFA
Requirements
NFA converted to equivalent DFA
1. Experimental purpose
1. Master the differences and connections between NFA and DFA;
2. Learn to use the subset construction method to convert NFA into the corresponding DFA.
2. Experimental environment
It is recommended to use Visual C++ 6.0; Windows series operating systems.
3. Experimental content and requirements
1. Input an NFA, use the subset construction method to convert the NFA into a DFA, and output the conversion diagram and conversion table of the DFA;
2. Determine whether the converted DFA is the simplest DFA. If not, output the simplest DFA.
4. Experimental process and results
1. Main principles of the algorithm
1. Read the input NFA information, including state transfer and empty transfer.
2. Initialize the initial state set nul[] as the starting state, and perform a closure operation on it through the nfakong function.
The states that can be reached by empty transfer are added to nul[].
3. Call the nfa function to perform state transfer operations based on the current state set lft[] and rgt[]. Traverse each state,
If there is a new state that can be reached by entering the characters ‘a’ or ‘b’, add it to the new set of states and pass
The nfakong function performs a closure operation on the new state set and adds the states that can be reached through empty transfer to the new state.
in collection.
4. Determine whether there is duplication between the new state set and the previous state set. If there is no duplication, the new state set will be
Add it to nul[] and continue with the next round of state transfer operations; if there are duplicates, discard the new state set.
5. Generate NFA state matrix output based on the transferred nul[] array.
6. Generate DFA state transition matrix output based on the transferred lft[] and rgt[] arrays.
2. Algorithm process and design ideas (recommended to draw illustrations)
1. Enter NFA information: First, the user needs to enter NFA information, including state transfer and empty transfer. by reading
Get the relevant data input by the user and store the state transition and empty transition information in the corresponding array.
2. Initialize the state set: Define the initial state set nul[] as the starting state, and add the starting state to nul[].
3. Closure operation: Implement closure operation on the state collection through the nfakong function. Traverse the current state collection, for
For each state, in the case of empty transition, find the state that can be reached through empty transition and add it to the new state set
Hit the mark. This process is carried out recursively until no more states can be found.
4.NFA conversion: Call the nfa function to perform NFA conversion based on the current state set lft[] and rgt[]. For each status
state, find the new state through the condition of state transition (character ‘a’ or ‘b’). Add the new state to the new state collection, and perform the closure operation on the new state collection again.
5. State set deduplication: Determine whether there are duplicates between the new state set and the previous state set. If there are no duplicates,
Then add the new state set to nul[] and continue with the next round of state transition operations; if there are duplicates, discard
Discard the new state collection.
6. Output NFA and DFA matrices: generate NFA state matrix sum based on the converted nul[], lft[] and rgt[] arrays
Output of the DFA state transition matrix. By traversing the array, the corresponding state collection and transition conditions are output to the console.
3. Experimental results and analysis (give at least 3 sets of test screenshots, including correct input and incorrect input examples, and
Provide verification instructions for the correctness of the results)
Attached source program and core code comments:
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 2048;
//The set passed by lft[]a, the set passed by rig[]b, the set passed by nul[] &
int a[maxn], b[maxn], kong[maxn], lft[maxn], rgt[maxn], nul[maxn];
//change[]convert nfa to dfa
char changea[maxn],changeb[maxn],changekong[maxn];
int count1 = 0, count2, q, p;
int index(int p) {//Find the corresponding status subscript
int x = 1;
if(p==1)
return 0;
int i = 0;
while ( + + i) { //Loop to find the current corresponding state subscript
x <<= 1;
if (p == x)
return i; //If found, return the corresponding subscript
}
return 0;
}
int moveT(int a, int b) {
while (b) {
int x = b & amp; (-b); //Get the last node in the current collection
if (!(a & amp; x)) //If the node does not exist, add it to the set
a^=x;
b ^= x; //The node already exists, so delete it
}
return a;
}
void nfakong(int p, char tchar) {
int nt = 0;
while (p) {
int x = p & amp; (-p); //Get the last node in the current collection
int y = index(x); //Find the corresponding state subscript
if (kong[y] != 0) {
if(tchar == 'a'){
lft[count1] |= kong[y];
}else if(tchar == 'b'){
rgt[count1] |= kong[y];
}else if(tchar == ' & amp;'){
nul[count1] |= kong[y];
}
nt = moveT(nt, kong[y]); //Perform move operation
}
p ^= x; //Remove the currently taken node from the original set
}
if (nt != 0){
if (tchar == 'a') {
nfakong(nt, 'a'); // Repeat operations
} else if (tchar == 'b') {
nfakong(nt, 'b'); // Repeat operations
} else {
nfakong(nt, ' & amp;'); // Repeat operations
}
}
}
void nfa(int p) {
int lsum = 0, rsum = 0;
while (p) {
int x = p & amp; (-p); //Get the last node in the current collection
int y = index(x); //Find the corresponding state subscript
if (a[y] != 0) {
lsum = moveT(lsum, a[y]); //Perform move operation
}
if (b[y] != 0) {
rsum = moveT(rsum, b[y]); //Perform move operation
}
p ^= x; //Remove the currently taken node from the original set
}
lft[count1] = lsum; //Update the current status collection
rgt[count1] = rsum; //Update the current status collection
if (lsum){
nfakong(lsum, 'a'); // Repeat operations
}
if (rsum){
nfakong(rsum, 'b'); // Repeat operations
}
}
void jihe(int p){
while(p){
int x = p & amp; (-p); //Get the last node in the current collection
int y = index(x); //Find the corresponding state subscript
cout<<y;
p ^= x; //Remove the currently taken node from the original set
if(p!=0){
cout<<",";
}
}
}
int main() {
int t;
cout << "Please enter the corresponding number of lines first:" << endl;
cin >> t;
cout << "Please enter NFA (& amp; represents empty string):" << endl;
while (t--) {
int preNode, nexNode;
char tchar;
cin >> preNode >> tchar >> nexNode;
if (tchar == 'a') {
a[preNode] |= (1 << nexNode);
} else if (tchar == 'b') {
b[preNode] |= (1 << nexNode);
} else {
kong[preNode] |= (1 << nexNode);
}
}
cout << endl;
cout << "Start status:";
cin >> q;
cout << "Accept status:";
cin >> p;
cout << endl;
//I initial state
nul[count1] = kong[q];
nfakong(kong[q], ' & amp;'); //Start conversion
nul[count1] |= (1 << q);
nfa(nul[count1]);
count2=count1;
int f,m;
while(count1>=count2){
f=0,m=0;
count1 + + ; //lef[] is input to nul[], left once
while(f<count1){ //Determine whether it is repeated
if(lft[count2]==nul[f]){
m=1;
break;
}
f + + ;
}
if(m==0){
if(lft[count2]==NULL){
count1--;
}
else{
nul[count1]=lft[count2];
nfa(lft[count2]);
}
}else{
m=0;
count1--;
}
count1 + + ;//rgt[] is input to nul[], right once
f=0,m=0;
while(f<count1){ //Determine whether it is repeated
if(rgt[count2]==nul[f]){
m=1;
break;
}
f + + ;
}
if(m==0){
if(rgt[count2]==NULL){
count1--;
}
else{
nul[count1]=rgt[count2];
nfa(rgt[count2]);
}
}else{
m=0;
count1--;
}
count2 + + ;
}
cout<<endl;
//Output nfa
cout<<"NFA state matrix:"<<endl;
cout<<"------------------------------------------------ -----------------------"<<endl;
cout<<"I initial state"<<" "<<"Ia"<<" "<<"Ib"<<endl;
cout<<"------------------------------------------------ -----------------------"<<endl;
for(int i=0;i<count2;i + + ){
jihe(nul[i]);
cout<<" ";
jihe(lft[i]);
cout<<" ";
jihe(rgt[i]);
cout<< endl;
changekong[i]='A' + i; //Mark the corresponding nul[] character
}
cout<<endl;
//output dfa
for(int i=0;i<count2;i + + ){
for(int j=0;j<count2;j + + ){
if(lft[i]==nul[j]){
changea[i]=changekong[j];
}
if(rgt[i]==nul[j]){
changeb[i]=changekong[j];
}
}
}
cout<<endl;
cout<<"DFA state transition matrix obtained from NFA:"<<endl;
cout<<"-------------------------"<<endl;
cout<<"I"<<" "<<"Ia"<<" "<<"Ib"<<endl;
cout<<"-------------------------"<<endl;
for(int i=0;i<count2;i + + ){
cout<<changekong[i]<<" "<<changea[i]<<" "<<changeb[i]<<endl;
}
return 0;
}