オートマトンNFAからDFAへの変換

質問

NFA(non-deterministic automaton)について質問させてください。
NFAからDFAへ変換するプログラムを作っています。
NFAの文法(状態数、アルファベット数、状態遷移表、終了状態）を別のデータファイルに入力し、それをプログラム中に読み込んで、NFAを登録したいと考えています。
しかし、状態遷移表だけがどのように取り込んでいいのか分からず途方に暮れています。
どうか教えていただけないでしょうか？
よろしく御願いいたします。
ファイルの中身（状態遷移表）としては、このような感じを考えています。
例えば、状態が３つ(q0, q1, q2)、３つのアルファベット(a,b,c)とε
0,1,2 E E E
E 1 E E
E E 2 1

q1から文字aのときにq0,q1,q2にそれぞれいくという意味。Eは何もなしという意味です。

回答No.2

sire · ベストアンサー

取りこみ方というよりは
データ構造について考慮中ということでしょうか？
>遷移の関数を用意したんですが、
>それに遷移元と遷移先とその時の文字
>そして次のデータへのポインタを一組
次のデータというのが良く分からないのですが、
ファイルの仕様として上のものをお考えでしたら
n行がq[n-1]状態を表し、
スペースで区切った時のm個目が(一般に言う)アルファベットのm番目の時の遷移先に対応するわけですよね。
Σ={a,b,c,,,z}、状態をq0・・・q99までと仮定し
状態のクラスを以下のように定義します。
#define E 100

// 状態を表すクラス
class State {
　// 遷移先状態
　int* pNextState['z' - 'a' + 1];
　public State(int iStateCount) {
　　// 遷移先を状態の数分作成しEにする
　　for (int i = 0;i < 'z' - 'a' + 1;i++) {
　　　pNextState[i] = new int [iStateCount];
　　　for (int n = 0;n < iStateCount;n++) {
　　　　pNextState[i][n] = E;
　　　}
　　}
　}
　public ~State() {
　　//デストラクタは略
　}
　// 次の遷移先を追加
　// cAlh その時の文字
　// iNextState 遷移先
　// 遷移先のインデックス
　public void AddState(char cAlh, int iNextState, int iIndex) {
　　pNextState[cAlh - 'a'][iIndex] = iNextState;
　}
　// 次の遷移先を取得
　// cAlh その時の文字
　// 非決定的に複数あった場合の遷移先のインデックス
　public int GetNextState(char cAlh, int iIndex) {
　　return pNextState[cAlh - 'a'][iIndex];
　}
}
このとき、あくまで配列を使って(STLを使えばいいのですが)上のファイルを読みこむと
まず状態を生成し
State sate[100];
1行目を読みこんで
初めのスペースまでで0,1,2と3つの遷移先が存在しますから、
sate[0].AddState('a',0,0);
sate[0].AddState('a',1,1);
sate[0].AddState('a',2,2);
となり、'a'の時はq0,q1,q2に行くという、q0状態が定義できます。
2行目を読みこんで
2番目のスペース前が1とありますので、
sate[1].AddState('b',1,0);
でq1状態が定義できます。

今q2状態で'b'が入ってきた時の遷移先は
state[2].GetNextState('b',0);
で取得できます。

とまぁこんなかんじで、状態遷移表と状態遷移関数を定義できないでしょうか(いまコンパイル環境がないのでソースは実行していませんが)。。
人によっていろいろ実装の仕方はありますし、上がベストではないですが、参考になれば幸いです。

お礼

sireさん
遅くなってすいません。
参考になりました。
なにかありましたら、またよろしくおねがいします。

回答No.1

sire

ファイルの中身の仕様としては、
スペース区切りが次の遷移先状態(の集合)
カンマ区切りが非決定的に複数の遷移があった場合の遷移先状態
ということですから、
1)1行読む
2)スペースで区切る→あるアルファベット遷移先状態(の集合)
3)2)の文字(列)をカンマで区切る→複数の遷移先状態
ということですよね。

どのようの取り込んでいいのか分からない、というのは読み込み方ですか？
であれば、strtokを使えば良いと思います。
http://www9.plala.or.jp/sgwr-t/lib/strtok.html
取り込んでの保持の仕方ですか？
|Q|(←状態の数)は先にファイルから読み込めば分かりますから、
|Q|個の配列を作っておけば、非決定的に複数の遷移先があっても保持できますよね(STL使えばいいんですが)

見当違いだったらすみません。

補足

参考になる回答ありがとうございます。
取り込み方についてもう少し詳しくご解説願えないでしょうか（とくに、0,1,2のところ）
実際遷移の関数を用意したんですが、それに遷移元と遷移先とその時の文字そして次のデータへのポインタを一組にして取り込みたいなと考えています。