これで私を助けてくれるといいのですが…。
正規表現がNFAおよび/またはDFAによって受け入れられるかどうかをどのように判断するかという主な質問があります。
たとえば。私の質問によると、正規表現のどれが同等ですか？説明...1。（a + b）** b（a + b）** b（a + b）*
2.a ba ba *
3.a ba b（a + b）*
NFAとDFAを描画してから、最小化アルゴリズムで見つける必要がありますか？そうすると、どの正規表現がNFA / DFAによって受け入れられるかをどのようにして知ることができるので、答えから始めることができますか？そのとても紛らわしい....
2つ目は非常によく似たもので、質問は言語（a ^ nb ^ n |n>1}がDFAによって受け入れられないことを示すように求めています...grrrrr...どうすればこれを知ることができますか？（ところでこれはいくつかのaの後に同じ数のbが続くすべての文字列のセット）...
はっきりと説明できたらいいのに…。
最初に、用語についての注意: 言語は、いくつかのアルファベットの文字列のセットです。DFA と NFA は、正規表現ではなく正規言語を認識します。同じ言語を定義する正規表現が複数存在する場合があります。2 つの言語 L1 と L2 の場合、L1 のすべてのメンバーが L2 のメンバーである場合、またはその逆の場合、L1 と L2 は同等です。
最初の質問に関して、言語 L1 は {a,b} 上のすべての文字列で構成され、少なくとも2 つの 'b' があります。言語 L2 は、正確に2 つの 'b'を持つ {a,b} 上のすべての文字列で構成されます。文字列「abbb」は L1 と L3 の要素ですが、L2 の要素ではありません。したがって、L1 と L3 を比較する必要があります。L1 の要素 S には、少なくとも 2 つの 'b' が含まれている必要があります。S の最初の 2 つの 'b' は、式 E3 の 2 つの明示的な 'b' と一致します。その場合、他のコンポーネントa*、a*、および(a+b)*は常に一致する可能性があり、S は L3 にある必要があります。したがって、L1 は L3 のサブセットです。同様に、L3 の要素 S には、少なくとも 2 つの 'b' が含まれている必要があります。それらが式 E1 の 2 つの明示的な 'b' と一致するようにします。その他のコンポーネント(a+b)*、(a+b)*、および(a+b)*も一致し、S も L1 に含まれます。したがって、L1 は L3 のサブセットであり、L3 は L1 のサブセットであるため、L1 と L3 は同等でなければなりません。
2 番目の質問について:ポンピング レンマを使用します。その言語を受け入れる DFA があるとします...言語に含まれていない文字列も受け入れる必要があることを示してください。したがって、そのような DFA は存在できません。S を言語の任意の文字列とします... S の任意の部分文字列は、すべて a か、すべて b か、またはその両方を持ちます...それを「ポンプ」した後はどうなりますか?
NFA と DFA は同等の (正規の) 言語を受け入れるため、言語が正規であることを示す 1 つの方法は、その言語の NFA または DFA を作成することです。
言語がクラスに含まれていないことを示すには、通常、ポンピング補題を使用します。
ウィキペディアには、n>=0 を除いて非常によく似た例があります。でも宿題は終わらせません。
http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages
2 つの正規表現が等しくないかどうかを判断するには、一方では受け入れられ、他方では拒否される文字列を作成します。
ある言語が DFA/NFA によって受け入れられないことを示すように求められた場合、ほとんどの場合、ポンピング補題を適用する必要があります。これはまさにその目的のために使用されます。