(ab+ba)*0 個以上の "a" の後に 0 個以上の "b" が続くすべて、および 0 個以上の "b" の後に 0 個以上の "a" が続くすべてを受け入れます。この RE の拒否状態は何ですか?
で受け入れられない文字列について考えてみて(ab+ba)*ください。
2 に答える
1
用語に関するいくつかの注意事項：正規表現には、拒否、受け入れ、またはその他の状態がありません。（純粋な）正規表現は正規言語を表します。正規言語にも状態はありません。言語の要素であるかどうかにかかわらず、文字列だけです。言語の補集合について議論することができます：言語の要素ではない同じアルファベット上の文字列のセット。たまたま、正規言語の補集合も正規言語です。すべての正規言語は有限オートマトンで記述でき、拒否状態または受け入れ状態を持つのはこのオートマトンです。
正規表現を与えて、その「拒否状態」を求めるのは正しくありません。同じ正規言語を記述するオートマトンが多数ある可能性があり、それらの可能性のどれを検討するかを指定する必要があります。
式（ab + ba）*で指定された言語ではない文字列の説明を求めていると仮定します。おそらく、（a + b）に関してこの言語の補数を説明する正規表現ですらあります。 *。
試みる可能性のあるアプローチの1つは、その言語を認識するDFAを見つけてから、すべての受け入れ状態を拒否状態に変更することです。その逆も同様です。結果として得られるDFAは、元の言語の補完を認識し、（ある程度の巧妙さをもって-読者の練習問題として残します）これを正規表現に戻すことができます。
于 2010-07-21T05:24:45.573 に答える
1
よく考えてみてください (これは重要です。これは宿題であり、理解する必要があります)。
あなたの説明に基づいて (あなたの実際の RE は非常に奇妙な形式であり、私が使用した RE 形式とはまったく異なります。より通常の RE 言語では、そうなるでしょうa*b*|b*a*)、最初に暗黙のアンカーがない限り、拒否条件はありません。および文字列の末尾 (その場合、aba拒否されます)。
すべての制約が「ゼロ以上」であるという事実は、すべての文字列が通過することを意味します。
于 2010-07-21T04:26:43.053 に答える