1

Python で DFA を最小化するアルゴリズムを見つけようとしています。私はいくつかの例を見つけましたが、それらはすべてコードにクラスがあります。現在、.txt ファイルに配置されている DFA の定義を転送してそれらのクラスに配置する方法がわかりません。.txt は次の方法でフォーマットされます。

  1. 行: コンマで区切られた一連の州を辞書順に並べたもの
  2. 行: コンマで区切られた一連のアルファベット記号を辞書順に並べたもの
  3. 行: コンマで区切られた許容可能な状態のセットで、辞書順に並べられています
  4. 行: 最初の状態
  5. その他のすべての行: 現在の状態、アルファベット記号->次の状態の形式の伝達関数

定義の例:

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

.txtファイルをロードします

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

lines = f.readlines()
4

1 に答える 1

0

これまでのところ、これはオートマトンの最小化とは何の関係もありませんよね? (指定された) ファイル形式からオートマトンを作成しようとしています。

これは宿題なので、いくつかのヒントを示します。

readlinesリストを返します。インデックスによって特定の行をアドレス指定できます。つまり、lines[0]最初の行、lines[1]、2 番目の行などです。これらの各行は文字列になります。たとえば、一連の状態 (lines[0]を保持する'dyny,fllf,gdci,gwtj,knos,kole,mjnw,msdl,mtfz,nbat,njgb,nzwx,rzpn,vcsc,zgfx') を含む行を使用すると、次のように使用できます。

lines[0].split(',')

コンマで分割すると、それぞれが状態を表す文字列のリストが得られます。個々の遷移を表すこれらの行は、もう少し複雑な形式に従います。

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

これらの行を解析して、上記の 3 つのコンポーネントを取得します。string.splitここでもあなたの友達です。また、遷移関数 (デルタ) に適したデータ構造を決定する必要があります。

注:readlinesファイル全体を一度に読み取ります。実際には、オートマトンは多くの場合非常に大きく、その場合はファイルをインクリメンタルに読み取る方がよいでしょう。ファイル オブジェクト (fコード内) は反復子プロトコルを実装し、ファイルの行を反復処理できるようにします。特に、使用することをお勧めします

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

最初の 4 行 (一連の状態を取得するなど) と、残り (遷移) を反復処理します。

for line in f:
    ...

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

于 2012-03-20T19:47:23.130 に答える