NFA(Nondeterministic Finite Automata) 시뮬레이션을 위한 C 프로그램

이 문제에서 우리는 비결정적 유한 오토마타(NFA)를 시뮬레이션하는 C 프로그램을 만들 것입니다.

NFA (Non-deterministic Finite automata) 입력 기호의 상태 조합으로 이동할 수 있는 유한 상태 기계입니다. 즉, 기계가 이동할 정확한 상태가 없습니다.

NDFA의 공식 정의 -

NFA / NDFA(Non-deterministic Finite automata)는 5-튜플(Q, ∑, δ, q0, F)로 나타낼 수 있습니다. 여기서 −

• Q는 유한 상태 집합입니다.

• ∑는 알파벳이라고 하는 유한한 기호 집합입니다.

• δ는 d:Q × ∑ → 2Q인 천이 함수입니다(NDFA의 경우 상태에서 Q 상태의 임의 조합으로 천이가 발생할 수 있기 때문에 여기에서 Q(2Q)의 거듭제곱 집합을 취했습니다.)

• q0은 입력이 처리되는 초기 상태입니다(q0 ∈ Q).

• F는 Q의 최종 상태/상태의 집합입니다(F ⊆ Q).

프로그래밍에서 NFA는 방향 그래프를 사용하여 생성됩니다. 그래프의 각 정점은 NDA의 상태를 나타냅니다. 그래프의 모서리는 0 또는 1의 두 값 중 하나를 가질 수 있습니다. 0으로 표시된 모서리는 비수용 전환을 나타내고 1로 표시된 모서리는 전환을 수락함을 나타냅니다.

그래프는 일반적으로 정점 1에서 유한 길이의 이진 배열인 입력 문자열을 취하는 진입점이 있습니다.

NFA 그래픽 형식을 보고 이를 이용하여 문법을 풀어봅시다.

시작 상태 -> 1

최종 상태(수락 상태) -> 4

문자열 01001이 허용되는지 여부를 확인합시다.

상태 1을 시작하고 0을 입력하면 0을 사용하여 상태 4로 이동하거나 자체 루프를 통해 상태 1로 이동할 수 있습니다.

우리는 두 경우 모두를 고려할 것입니다 -

{1->1} 1001{1->4} 1001

상태 1/4, 입력 1 -

상태 1에서 우리는 2 또는 자체 루프로 갈 수 있고, 상태 4에서 더 갈 수 없으므로 이 케이스를 버립니다.

우리는 하나의 사례를 고려할 것입니다 -

{1->1->1} 001{1->1->2} 001

상태 1/2, 입력 0 -

상태 1에서 4 또는 자체 루프로 갈 수 있고, 상태 2에서 4 또는 자체 루프로 갈 수 있습니다.

우리는 모든 경우를 고려할 것입니다 -

{1->1->1->1} 01{1->1->1->4} 01{1->1->2->1} 01{1->1->2 ->4} 01

상태 1/2/4, 입력 0 -

상태 1에서 4 또는 자체 루프로 갈 수 있고, 상태 2에서 4 또는 자체 루프로 갈 수 있고, 상태 4에서 3 또는 자체 루프로 갈 수 있습니다.

우리는 모든 경우를 고려할 것입니다 -

상태 1/2/3/4, 입력 1 -

상태 1에서 2 또는 자체 루프로 갈 수 있습니다. 상태 2에서 3으로 갈 수 있고, 상태 3에서 4로 갈 수 있으며, 상태 4에서 더 이상 갈 수 없습니다.

우리는 모든 경우를 고려할 것입니다 -

{1->1->1->1->1->1/2}이 최종 단계에 도달하지 않음{1->1->1->1->4} 1 입력을 수락할 수 없음{1->1->1->4->3 ->4} 입력 허용{1->1->1->4->4} 입력 허용 불가{1->1->2->1->1 -> 1/2} 최종 단계에 도달하지 않음{1->1->2->1->4} 입력을 수락할 수 없음{1->1->2->4->3->4} 입력을 수락함 {1->1->2->4->4} 입력을 수락할 수 없습니다.

따라서 주어진 입력 문자열로 최종 상태에 도달하는 방법이 있습니다.

이제 NFA(Nondeterministic Finite Automata)를 시뮬레이션하는 C 프로그램으로 가 보겠습니다. -

프로그램의 입력은 NFA의 인접 목록이 됩니다 -

에지 수(n)

에지 연결(n 라인)

확인할 문자열

예시

41031204211043010412044120114101101

출력

예/아니오

예시

#include #include #include #include #include int row =0;struct node{ int data; 구조체 노드* 다음; char edgetype;}typedef node;// 인접 listnode*에 에지를 추가합니다. push(node* first , char edgetype , int data){ node* new_node =(node*)malloc(sizeof(node)); new_node-> edgetype =edgetype; new_node->data =데이터; new_node->다음 =NULL; if (첫 번째==NULL){ 첫 번째 =new_node; 반환 new_node; } 첫 번째->다음 =푸시(첫 번째->다음, 에지 유형, 데이터); return first;}//input의 수락 여부를 확인하는 재귀 함수int nfa(node** graph, int current, char* input,int* accept, int start){ if (start==(int)strlen(input)) return accept [현재의]; 노드* 온도 =그래프[현재]; while (temp !=NULL){ if (input[start]==temp->edgetype) { if (nfa(graph,temp->data,input,accept,start+1==1)){ return 1; } } 임시 =임시 -> 다음; } return 0;}//크기 nvoid generate(char** arr, int size, char *a){ if (size==0){ strcpy(arr[row], a); 행++; 반품; } 문자 b0[20] ={'\0'}; 문자 b1[20] ={'\0'}; b0[0] ='0'; b1[0] ='1'; 생성((char**)arr, 크기-1, strcat(b0,a)); //앞에 0 추가 generate((char**)arr, size-1, strcat(b1,a)); //앞에 1 추가 return;}int main(){ int n; 정수 i, j; scanf("%d", &n); //노드 수 node* graph[n+1]; //(i=0;i 
입력
 
41 0 4 0 1 0 2 1 1 1 32 0 1 0 43 0 1 1 44 1 2 0 4 1 4
 
출력
 
001100000101110011011100000001