Pythonでdfaを最小化する

Question

私はPythonでDFAを最小化するアルゴリズムを見つけようとしています。私はいくつかの例を見つけました。それらはすべてコードでクラスを持っています。今、私は.txtファイルに置かれたDFAの定義をどのように転送してそれらのクラスに入れるのか分かりません。

1. ライン：カンマで区切られた状態の集合、辞書順
2. ライン命じ：カンマで区切られたアルファベット記号の集合、辞書順
3. ラインを命じた：セット.txtファイルは次のようにフォーマットされています最初の状態
4. および他のすべての行：フォーマット現在の状態の伝達関数、アルファベットシンボル - >次に状態

辞書

ライン順序付けカンマで区切られた許容される状態、の定義の

例：クラスの

dyny,fllf,gdci,gwtj,knos,kole,mjnw,msdl,mtfz,nbat,njgb,nzwx,rzpn,vcsc,zgfx 

b,d,e,f,g,k,l,m,n,o,p,q,r,t,u,w 

dyny,njgb,zgfx 

mtfz 

dyny,b->rzpn 

dyny,d->msdl 

dyny,e->gdci 
. 
. 
. 

例は

class DFA: 

    def __init__(self, states, alphabet, delta, start, accepts): 
     self.states = states 
     self.start = start 
     self.delta = delta 
     self.accepts = accepts 
     self.alphabet = alphabet 
     self.current_state = start 

は、私がこれまで

f = open('definition.txt','r') 

lines = f.readlines() 

Answer 1

で.txtファイルをロードし、これはとは何の関係もありませんオートマタの最小化、そう？いくつかの（与えられた）ファイル形式からオートマトンを作成しようとしています。

これは宿題ですので、私はあなたにいくつかのヒントをあげる：

readlinesは、リストを返します。特定の行をインデックスで指定することができます。つまり、最初の行にはlines[0]、次の行にはlines[1]、次は です。これらの各行は文字列になります。 、それぞれ表す取ると、例えば、（'dyny,fllf,gdci,gwtj,knos,kole,mjnw,msdl,mtfz,nbat,njgb,nzwx,rzpn,vcsc,zgfx'を保持lines[0]、）状態の集合を含む行は、あなたがあなたの文字列のリストを与えるコンマ、でそれを分割する

lines[0].split(',')

を使用することができます状態。個々の遷移を表し、それらの行は、もう少し複雑なフォーマットに従ってください：あなたは上記の描写の3つのコンポーネントが得られるように

<state>','<input symbol>'->'<next state>

あなたはそれらの行を解析します。 string.splitはここでもあなたの友人です。また、遷移関数（デルタ）に適したデータ構造を決定する必要があります。

注：readlinesは、ファイル全体を一度に読み取ります。実際には、オートマトンはしばしば非常に大きく、その場合、ファイルを徐々に読み込むほうがよいでしょう。ファイルオブジェクト（コード内のf）はイテレータプロトコルを実装しており、ファイルの行を繰り返し処理することができます。特に、私は（など、状態の集合を取得するには）最初の4行のため

line1 = f.next() # Next line (first line, if first call of next) 
line2 = f.next() # Next line 
... 

を使用することをお勧めし、残りを反復する（トランジション）：

for line in f: 
    ... 

http://docs.python.org/tutorial/inputoutput.htmlを参照してください。詳細については。