C言語で非決定性有限オートマトン（NFA）をシミュレートする方法

この記事では、非決定性有限オートマトン（NFA）をシミュレートするCプログラムの作成方法について解説します。

NFA（Non-deterministic Finite Automata：非決定性有限オートマトン）とは、ある入力記号に対して複数の状態への遷移が可能な有限状態機械のことです。つまり、入力に対して機械がどの状態に移動するかが一意に定まらない点が特徴です。

NFAの形式的定義

NFA／NDFA（非決定性有限オートマトン）は、次の5つ組（Q, Σ, δ, q0, F）で表現できます。

• Q：状態の有限集合

• Σ：アルファベットと呼ばれる記号の有限集合

• δ：遷移関数。δ: Q × Σ → 2^Q（ここでQの冪集合2^Qを用いるのは、NDFAでは1つの状態からQの任意の状態の組み合わせへ遷移できるため）

• q0：初期状態。すべての入力処理はここから始まる（q0 ∈ Q）

• F：最終状態（受理状態）の集合（F ⊆ Q）

NFAのグラフ表現

プログラミングにおいて、NFAは有向グラフとして構築されます。グラフの各頂点がNFAの状態を表し、辺には0または1のいずれかのラベルが付きます。ラベル0の辺は非受理遷移を、ラベル1の辺は受理遷移を意味します。

グラフには通常、頂点1を起点とする入口があり、そこから有限長のバイナリ配列である入力文字列を受け取ります。

それでは、NFAをグラフ形式で確認し、実際に文法を解いてみましょう。

• 開始状態 → 1
• 最終状態（受理状態）→ 4

文字列「01001」が受理されるか検証する

開始状態1、入力0の場合、0によって状態4へ遷移するか、状態1で自己ループするかの2通りがあります。

両方のケースを考慮します。

{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->1->1->1->1} 1
{1->1->1->1->4} 1
{1->1->1->4->3} 1
{1->1->1->4->4} 1
{1->1->2->1->1} 1
{1->1->2->1->4} 1
{1->1->2->4->3} 1
{1->1->2->4->4} 1

状態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->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} 入力を受理できず

このように、与えられた入力文字列で最終状態に到達できる経路が存在するため、文字列「01001」は受理されます。

NFAをシミュレートするCプログラム

次に、非決定性有限オートマトン（NFA）をシミュレートするCプログラムを見ていきましょう。

プログラムへの入力は、NFAの隣接リストです。

• 辺の数（n）
• 辺の接続情報（n行）
• 判定対象の文字列

入力例

4
1031204
21104
301041204
4120114
101101

出力例

Yes/No

C言語での実装コード

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
int row = 0;
struct node{
    int data;
    struct node* next;
    char edgetype;
}typedef node;
// 隣接リストに辺を追加する関数
node* push(node* first , char edgetype , int data){
    node* new_node = (node*)malloc(sizeof(node));
    new_node->edgetype = edgetype;
    new_node->data = data;
    new_node->next = NULL;
    if (first==NULL){
        first = new_node;
        return new_node;
    }
    first->next = push(first->next,edgetype,data);
    return first;
}
// 入力の受理を再帰的に判定する関数
int nfa(node** graph, int current, char* input,
int* accept, int start){
    if (start==(int)strlen(input))
    return accept[current];
    node* temp = graph[current];
    while (temp != NULL){
        if (input[start]==temp->edgetype) {
            if (nfa(graph,temp->data,input,accept,start+1==1)){
                return 1;
            }
        }
        temp=temp->next;
    }
    return 0;
}
// サイズnのバイナリ文字列を生成する関数
void generate(char** arr, int size, char *a){
    if (size==0){
        strcpy(arr[row], a);
        row++;
        return;
    }
    char b0[20] = {'\0'};
    char b1[20] = {'\0'};
    b0[0] = '0';
    b1[0] = '1';
    generate((char**)arr, size-1, strcat(b0,a)); //先頭に0を追加
    generate((char**)arr, size-1, strcat(b1,a)); //先頭に1を追加
    return;
}
int main(){
    int n;
    int i, j;
    scanf("%d", &n); //ノード数
    node* graph[n+1]; //グラフを作成
    for (i=0;i<n+1;i++)
    graph[i]=NULL;
    int accept[n+1]; //頂点の状態を格納する配列
    for (i=0; i<n; i++){
        // 頂点のインデックス、受理状態、辺の数
        int index,acc,number_nodes;
        scanf("%d%d%d",&index,&acc,&number_nodes);
        accept[index]=acc; //受理状態を保存
        for (j=0;j<number_nodes;j++){
            int node_add;
            int edge;
            scanf("%d%d",&edge,&node_add);
            graph[index] = push(graph[index],'0'+edge,node_add);
        }
    }
    int size = 1; //入力サイズ
    int count = 0; //出力文字列のカウント
    if (accept[1]==1){ //空文字列のチェック
        printf("e\n");
        count++;
    }
    while (count < 11){
        char** arr;
        int power = pow(2,size);
        arr = (char**)malloc(power*sizeof(char*));
        for (i=0;i<power;i++)
            arr[i] = (char*)malloc(size*sizeof(char));
        char a[20] = {'\0'};
        generate((char**)arr,size,a); //入力を生成
        for (i=0; i<power; i++){
            char input[20] = {'\0'};
            for (j=0; j<size; j++){
                char foo[2];
                foo[0] = arr[i][size-1-j];
                foo[1] = '\0';
                strcat(input,foo);
                //生成した文字列をinputにコピー
            }
            int result = nfa(graph,1,input,accept,0);
            //NFAの判定結果を保存
            if (result==1){
                printf("%s\n",input);
                count++;
            }
            if (count==10)
            return 0;
        }
        size++; //バイナリ文字列入力のサイズを増加
        row=0;
    }
    return 0;
}

入力

4
1 0 4 0 1 0 2 1 1 1 3
2 0 1 0 4
3 0 1 1 4
4 1 2 0 4 1 4

出力

00
11
000
001
011
100
110
111
0000
0001