NFA 의 확정 화

실험 1 NFA 의 확정 화
실험 목적
1. 이번 실험 을 통 해 정규 표현 식, NFA, DFA 와 그 가 식별 하 는 언어 에 대한 이 해 를 강화 합 니 다.
2. NFA 에서 DFA 로 의 전환 을 파악 하고 부분 집합 법 으로 NFA 를 DFA 이론 으로 전환 시 키 며 프로 그래 밍 은 NFA (가난 한 자동 동기 가 있 는 지 확실 하지 않 음) 를 DFA 로 전환 하 는 것 을 실현 한다.
 
실험 내용
주어진 NFA (5 원조) 를 확정 화하 고 등가 의 DFA 를 출력 합 니 다.적합 한 NFA 의 저장 형식 을 선택 하고 정확성 검 사 를 요구 합 니 다.
 
3. 실험 원리
확실한 유한 자동 동기 (DFA) M 은 5 원 그룹, M = (K, ＞, F, S, Z) 으로 정의 할 수 있다. 그 중에서:
（1） K 는 빈 공간 이 있 고 집합 중의 모든 요 소 를 하나의 상태 라 고 부른다.
（2） ∑ 는 가난 한 자모표 로 ∑ 중의 모든 원 소 를 하나의 입력 기호 라 고 부른다.
（3） F 는 K 에서×← K 의 단일 값 변환 함수, 즉 F (R, a) = Q, (R, Q * 8712 ° K) 는 현 재 를 나타 낸다.
상 태 는 R 이 고 문자 a 를 입력 하면 상태 Q 로 이동 하 며 상태 Q 는 상태 R 의 후계 상태 라 고 합 니 다.
（4） S * 8712 ° K 는 유일한 초기 상태 입 니 다.
（5） Z * 8712 ° K 는 종 태 집합 입 니 다.
불확실 한 자동 동기 (NFA) M 은 5 원 그룹, M = (K, ＞, F, S, Z) 으로 정의 할 수 있다. 그 중에서:
（1） k 는 빈 공간 이 있 고 집합 중의 모든 요 소 를 하나의 상태 라 고 부른다.
（2） ∑ 는 가난 한 자모표 로 ∑ 중의 모든 원 소 를 하나의 입력 기호 라 고 부른다.
（3） F 는 K 에서×← K 의 부분 집합 전환 함수;
（4） S * 8712 ° K 는 비어 있 지 않 은 초기 상태 집합 입 니 다.
（5） Z * 8712 ° K 는 종 태 집합 입 니 다.
정 의 를 통 해 알 수 있 듯 이 유한 한 자동 동기 NFA 와 유한 한 자동 동기 DFA 의 주요 차이 점 은 다음 과 같다.
(1) NFA 의 초기 상태 S 는 하나의 상태 집합 으로 여러 개의 초기 상 태 를 허용 합 니 다.
(2) NFA 에서 상 태 를 특정한 출력 변 에 똑 같은 기호 가 있 도록 허용 한다. 즉, 같은 입력 기호 에 여러 개의 후계 상 태 를 가 질 수 있다.즉 DFA 의 F 는 단수 함수 이 고 NFA 의 F 는 다수 함수 이다.
따라서 유한 한 자동 동기 DFA 를 확정 하 는 것 은 유한 한 자동 동기 NFA 를 확정 하지 못 하 는 특례 로 볼 수 있 고 DFA 가 받 아들 일 수 있 는 기호 문자열 은 반드시 NFA 에 의 해 받 아들 여 질 수 있다.모든 NFA 에 대해 M1 에는 항상 DFA 가 존재 합 니 다. M2, L (M1) = L (M2).즉, 유한 한 자동 동기 가 받 아들 일 수 있 는 언어 는 등가 의 확정 유한 한 자동 동 기 를 찾 아 이 언어 를 받 아들 일 수 있다. 。
 
알고리즘 사상
1. 부분 집합 구조 법 에 따라 NFA 확정 화
  (1) I 가 M '의 상태 집합의 부분 집합 이 라 고 가정 하고 집합 I 의ε폐쇄 하 다ε-closure (I) 는:
       s * 8712 ° I 면 s * 8712 °ε-closure（I）；
       s * 8712 ° I 면 s 에서 출발 하여 임의의 항목 을 지나 갑 니 다.ε아크 가 도달 할 수 있 는 모든 상 태 는ε-closure（I）。
 (2) I 가 M '의 상태 집합의 부분 집합 이 라 고 가정 하고 Ia =ε__CLOSURE (J), 그 중에서 J 는 I 중의 어떤 상태 결점 에서 출발 하여 a 호 를 지나 도착 할 수 있 는 상태 결점 의 전체 이다.
(3) K + 1 열 이 있 는 표 (K 는 개수 변환) 를 구성 합 니 다. 이 표 의 첫 번 째 열 은?ε-closure（X）。이 줄 의 모든 상태 부분 집합 을 확인 하고 표 의 첫 번 째 열 에 나타 나 지 않 은 사람 을 뒤의 빈 줄 의 첫 번 째 열 에 채 워 넣 습 니 다.상기 과정 을 반복 하면 I + 1 열 에 나타 날 때 까지 모든 상태 서브 집합 이 첫 번 째 열 에 나타난다.
2. DFA 의 간소화
  종 태 그룹 과 비 종 태 그룹의 Ik (k = a, b...) 를 구하 고 모든 집합 이 그룹 집합의 부분 집합 이면 DFA 는 최소 화 되 었 습 니 다.
구체 적 실현

#include 
#define MAXS 100
using namespace std;
string NODE;//    
string CHANGE;//     
int N;//NFA  

struct edge{
	string first;
	string change;
	string last;
};
struct chan{
	string ltab;
	string jihe[MAXS];
};
void kong(int a){
	int i;
	for(i=0;iNODE.find(a[i+1])){
b=a[i];
a[i]=a[i+1];
a[i+1]=b;
}
} 
void eclouse(char c,string &he,edge b[]){
int k;
for(k=0;khe.length())
he+=b[k].last;
eclouse(b[k].last[0],he,b);
}
}
}
void move(chan &he,int m,edge b[]) {
int i,j,k,l;
k=he.ltab.length();
l=he.jihe[m].length();
for(i=0;ihe.jihe[m].length())
he.jihe[m]+=b[j].last[0]; 
for(i=0;ihe.jihe[m].length())
he.jihe[m]+=b[j].last[0];
} 
/ / 출력
void outputfa(int len,int h,chan *t){
int i,j,m;
cout<>b[i].first;
if(b[i].first=="#") break;
cin>>b[i].change>>b[i].last; 
}
N=i;
for(i=0;iNODE.length())
NODE+=b[i].first;
if(NODE.find(b[i].last)>NODE.length())
NODE+=b[i].last;
if((CHANGE.find(b[i].change)>CHANGE.length())&&(b[i].change!="*"))
CHANGE+=b[i].change;
}
len=CHANGE.length();
cout<>endnode;
for(i=0;iNODE.length()){
cout<";
move (t [i], k, b); / / move (I, a)
//cout<ednode.length())
d[0]+=NODE[i];
endnode=ednode;
cout<