6

部分文字列を含まないs とsのすべての文字列からなる言語を定義する正規表現を作成する問題に取り組んでいます ( Hopcroft、Motwani、Ullman によるAutomata Theory, Languages and Computer の紹介から) 。01011

答えは(0+1)* - 011正しいですか?そうでない場合、これに対する正しい答えは何ですか?

4

2 に答える 2

11

オートマトン図 編集:以下のコメントに従って、開始状態と修正を含むように更新されました。

于 2010-04-17T10:58:26.437 に答える
5

011文字列を単純に除外するのではなく、部分文字列として持たないすべての文字列を探している場合011:

そのための古典的な正規表現は次のようになります。

1*(0+01)*

基本的に、最初に好きなだけ 1 を付けることができますが、0 にヒットするとすぐに、0 または 0-1 が続きます (そうしないと 0-1-1 になるため)。

現代的で、あまり規則的ではない正規表現は次のようになります。

^((?!011)[01])*$

ただし、 ではない文字列が必要な場合は011、短い文字列を列挙し、残りをワイルドカードにするだけです。

λ+0+1+00+01+10+11+(1+00+010)(0+1)*

そして現代の正規表現では:

^(?!011)[01]*$
于 2010-04-17T10:00:09.210 に答える