正規表現についても教える計算コースを受講しています。答えられない難しい質問があります。
最大で2組の連続する0を含む単語を受け入れる言語の正規表現を見つけます。アルファベットは0と1で構成されます。
最初に、その言語のNFAを作成しましたが、それをGNFAに変換できません（後で正規表現に変換されます）。この通常の表現をどのように見つけることができますか？GNFAに変換するかどうか？
2767 次
3 に答える
3
（これは宿題の問題なので、完全に機能する解決策ではなく、始めるのに十分な助けが必要だと思いますか？）
マイレージは異なる場合がありますが、NFAを正規表現に変換することはお勧めしません。この2つは理論的には同等であり、どちらもアルゴリズムでもう一方に変換できますが、私の意見では、どちらかを構築するのに最も直感的な方法ではありません。
代わりに、1つのアプローチは、さまざまな可能性を列挙することから始めることです。
連続するゼロのペアはまったくありません。つまり、文字列の最後を除いて、すべてのゼロの後に1を付ける必要があります。したがって、文字列はとの混合シーケンスで構成され
1、オプションで：01が続きます。0(1|01)*(0|ε)文字列の最後にある、正確に1組の連続するゼロ。これは前のものと非常に似ています：
(1|01)*00文字列の終わりではなく、正確に1組の連続するゼロ—したがって、必ず1が続きます。これも最初のものと非常に似ています：
(1|01)*001(1|01)*(0|ε)
このアプローチを続けるには、上記を拡張して、2組の連続するゼロをサポートします。最後に、これらすべてを1つの正規表現にマージします。
于 2012-03-17T18:17:09.537 に答える
0
（0 + 1）* 00（0 + 1）* 00（0 + 1）* +（0 + 1）* 000（0 + 1）*
于 2015-07-08T09:22:23.167 に答える
-1
連続する0の最大2つのペアが含まれます
(1|01)*(00|ε)(1|10)*(00|ε)(1|10)*
于 2013-03-09T21:38:35.810 に答える