regex - 正規表現の補数を見つける方法

Question

補数が正規表現 0* で表されるアルファベット {0,1} に対する言語 L の正規表現を与えてください

答えは 1^+ だと思いますが証明できません 助けてください

Answer 1

まず第一に、ダニエルは答えが「少なくとも 1 つの 1 を含むすべての単語」であることは正しいです。しかし、どうやってそれを証明できますか？

正規表現の補数は、有限オートメーション表現を使用して最も簡単に構築できます。次の画像を参照してください。

左のボックスは の DFA を示しています0*。その補完を構築するために必要なことは、すべての非受け入れ状態を受け入れ状態にすること、およびその逆を行うことだけです。これは右の画像で行われます。

さて、あなたはそこまでの道のりを歩んでいますが、今度はそこから正規表現を構築する必要があります。これは確かにあなたの教科書または同等のもので説明されていますが、それが見つからない場合は、ここにアルゴリズムを説明する pdf があります。

(A = 状態 1) および (F = 状態 2) で提供されるアルゴリズムを使用すると、次のようになります。

R_11^0 = ɛ|0
R_12^0 = 1
R_21^0 = (empty set)
R_22^0 = ɛ|0|1

R_ij^1 に移ると、次のようになります。

R_11^1 = (ɛ|0) | (ɛ|0)(ɛ|0)*(ɛ|0) = (ɛ|0)* = 0*
R_12^1 = 1 | (ɛ|0)(ɛ|0)*1 = 1 | 0+1 = 0*1
R_21^1 = (empty set) | (empty set)(ɛ|0)*(ɛ|0) = (empty set)
R_22^1 = (ɛ|0|1) | (empty set)(ɛ|0)*1 = (ɛ|0|1)

そして最終段階：

R_11^2 = 0* | (0*1)(0|1)*(empty set) = 0*
R_12^2 = 0*1 | (0*1)(ɛ|0|1)*(ɛ|0|1) = (0*1)(0|1)* = 0*1(0|1)*   <------- !!! HERE !!!
R_21^2 = (empty set) | (ɛ|0|1)(ɛ|0|1)*(empty set) = (empty set)
R_22^2 = (ɛ|0|1) | (ɛ|0|1)(ɛ|0|1)*(ɛ|0|1) = (ɛ|0|1)

これで、開始状態を最初のインデックスとして、受け入れ状態を最後のインデックスとして持つすべての結果を調べることで、正規表現を見つけることができます。この例では、状態 1 (A) が唯一の開始状態であり、状態 2 (F) が唯一の受け入れ状態であるため、結果はR_12^2次のようになります。

0*1(0|1)*

簡単な英語では、次のようになります。

• 好きなだけゼロ
• ワン（！）
• そして、あなたが好きなだけのゼロまたは1

つまり、少なくとも 1 つの単語を含むすべての単語です。

Answer 2

言語の補数 ( ^0*$) には、空の単語とゼロのみで構成されるすべての単語が含まれます。したがって、言語には、ゼロだけで構成されていないすべての単語が含まれています。つまり、少なくとも 1 つのゼロが含まれています。したがって、言語の正規表現は^.*1.*$. アルファベットを考慮し、正規表現の 1 つを最初のものにすることは、 と同等^0*1(0|1)*$です。