言語が正規表現を与えることによって規則的であることを証明する

StackOverflow https://stackoverflow.com/questions/3868010

  •  28-09-2019
  •  | 
  •  

質問

私はこの実践の問題に困惑しています（マーク用ではありません）：

{wは{a、b}*の要素です：aの数は偶数であり、bの数は均等です}

私はこれを理解できないようです。この場合、0は偶数と見なされます。いくつかの許容される文字列：{}、{aa}、{bb}、{aabb}、{abab}、{bbaa}、{babaabba}など

Aがプレフィックスである必要があり、答えが次のような場合も同様の例を作成しました。（AA）（BB）しかし、この場合、彼らはどんな順序でもあります。

Kleene Stars（*）、組合（U）、交差（＆）、および連結を使用することができます。

編集：これにも問題があります

{wは{0,1}*の要素です：w = 1^r 0 1^s 0の場合、r、s> = 1}

役に立ちましたか？

解決

これは醜いですが、うまくいくはずです：

ε U ( (aa) U (bb) U ((ab) U (ba) (ab) U (ba)) )*

2番目の場合：

11*011*0

一般的に使用します a+ それ以外の aa* ここ。

他のヒント

編集: ：削除されていないRe：Nulluserexceptionの答えのコメント。

1）個人的には、最初に文字列を受け入れることができるDFAを構築する場合、これは概念化が簡単だと思います。私はそれを書き留めていませんが、私の頭の上から外れて、あなたは4つの州と1つの州でこれを行うことができると思います。そこから、次のようなアルゴリズムを使用して、一度に状態を1つずつ除去することにより、同等の正規表現を作成できます。 これです. 。これは、DFAと正規表現が実証されているため、可能です。

2）クリーンの星が最も近い正規表現にのみ適用されるという事実を考慮してください。したがって、2つの個別のグループ化されていない原子がある場合（原子自体はregexです！）、2番目の原子にのみ適用されます（ように、 ab* 単一のaと次に、0 -bを含む任意の数字に一致します。何かが存在したい場合には、これを有利に使用できますが、何があるかわからない。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top