1

質問：

5 つの連続する位置のすべてのブロックに少なくとも 2 つの 0 が含まれるように、{0,1} を超えるすべての文字列を受け入れる DFA を定義します。質問をよく読んでください。これにより、e (イプシロン (空の文字列)) を受け入れることができるでしょうか? 0101はどうですか？このような英語の説明はさまざまな本に見られるので、読み方と解釈方法を知っておいてもらいたいと思います。

講師へのヒント: 「「5 ブロック」の DFA は、プログラムで問題なく生成できます。私は両方の方法で (手動とプログラムで) 作成しました。私は Emacs とキーボード マクロが得意なので、「手動」でも作成できました' 機械的かつ非常に高速ですが、プログラムはエラーが発生しにくく、コンパクトです。"

私はこのことを描いていますが、制御不能になっているので、間違っていると思います。

Pythonで作成する前のDFAのスケッチ： ここに画像の説明を入力

ただし、インデックス 2、3、4、5、および 6 は 5 つの連続した位置のブロックを構成するため、これは正しくありません。そのため、少なくとも 2 つのゼロを考慮する必要があります。2 つの 0 ではなく 2 つの 1 が必要だと思っていました。私はこれを完全に間違った方法で行っていますか? 私が考えているように、これには膨大な量の状態があるからです。

(この大きな DFA の描画に戻ります)

4

3 に答える 3

2

これを行う方法は、最後の 5 ビットを表す、考えられる 5 ビット文字列ごとに状態を定義することです。00000 を表す状態から開始し、状態から状態へと自然に移動し、各状態を 2 つ以上のゼロで承認としてマークします。

于 2012-09-17T04:43:46.587 に答える
1

古い学校の方法でやりたい場合：

def check(s):
    buffer = s[:5]
    i = 5
    count0, count1 = 0, 0
    while i < len(s):
        if len(buffer) == 5:
            first = buffer[0]
            if first == '0':
                count0 -= 1
            else:
                count1 -= 1
            buffer = buffer[1:]
        buffer += s[i]
        if buffer[-1] == '0':
            count0 += 1
        else:
            count1 += 1
        if count0 < 2:
            return "REJECT"
        i += 1
    if buffer.count('0') >= 2:
        return "ACCEPT"
    else:
        return "REJECT"

少し賢い方法：

def check(s):
    return all(ss.count('0')>=2 for ss in (s[i:i+5] for i in xrange(len(s)-4)))

上記のメソッドの詳細コード:

def check(s):
    subs = (s[i:i+5] for i in xrange(len(s)-4))
    for sub in subs:
        if sub.count('0') < 2:
            return "REJECT"
    return "ACCEPT"

このコードはまだテストしていませんが、うまくいくはずです。あなたの教授はおそらく3番目の方法を望んでいます。

お役に立てれば

于 2012-09-17T04:33:35.207 に答える
1

実際には、単一の拒否状態を含めて、11 16 の状態があります。状態は、最新の 2 番目のゼロで切り捨てられた最大 4 文字の履歴に対応します。トランジションはブロック内の 5 番目の文字を構成するため、必要な文字は 4 文字だけです。遷移文字が 0 ではなく、4 文字の履歴に 2 つのゼロがない場合、遷移は失敗します。

Python を記述するよりも入力する方が速いため、遷移を手動で生成しました。そのため、一般化された (k, n) (n のブロック内の k 個のゼロ) 問題は、コーディングの演習として残します。(州名に x を挿入して、並べやすくしました。)

sxx00 (0)->sxx00 (1)->sx001
sx001 (0)->sx010 (1)->s0011
sx010 (0)->sxx00 (1)->s0101
s0011 (0)->s0110 (1)->s0111
s0101 (0)->sx010 (1)->s1011
s0110 (0)->sxx00 (1)->s1101
s0111 (0)->s1110 (1)->sFAIL
s1011 (0)->s0110 (1)->sFAIL
s1101 (0)->sx010 (1)->sFAIL
s1110 (0)->sxx00 (1)->sFAIL
sFAIL (0)->sFAIL (1)->sFAIL

[編集]: (質問を読んだときに) 文字列 '1111' を受け入れる必要があるため、これは実際にはまったく正しくありませんでした。(5 文字のブロックは存在しないため、その中のすべての 5 文字のブロックには 2 つのゼロがあります。) したがって、いくつかの追加の起動状態があります。

start (0)->sxx00 (1)->s1
s1    (0)->sx010 (1)->s11
s11   (0)->s0110 (1)->s111
s111  (0)->s1110 (1)->s1111
s1111 (0)->sFAIL (1)->sFAIL

最後の状態は sFAIL によく似ていますが、受け入れ状態であるため異なります。

于 2012-09-17T04:56:21.093 に答える