regex - 正規言語から正規表現を導出する

Question

以下の言語を考えると、その言語の正規表現を見つけるにはどうすればよいですか？

L = {a ^ nb ^ m | n => 1、m => 1、nm => 3}

score 5 · Accepted Answer

n>=1およびm>=1およびnm>=3は、次のそれぞれに当てはまります。

n = 1、m> = 3

n> = 3、m = 1

n> = 2、m> = 2

したがって、L = {abbb、abbbb、abbbbb、...} U {aaab、aaaab、aaaaab、...} U {a ^ nb ^ m | n> = 2、m> = 2}

この正規表現はLと同等である必要があります。

（（abbb（b *））|（aaa（a *）b）|（aa（a *）bb（b *）））

おそらくこれよりもはるかに簡潔な答えがあります。

score 3 · Accepted Answer

その言語の単語の例を書き留めます。それらを感じてください。パターンを探します。一般的なプレフィックス/サフィックス/サブストリングを探します。

abbb
abbbb
abbbbb
aabb
aabbb
aabbbb
aaab
aaabb
aaabbb
aaaab
aaaabb
aaaabbb

例: すべての単語はで始まり、aで終わることに注意してbください。したがって、正規表現は次のようになりa...bます。部品はどの...ように見えますか？

bb
bbb
bbbb
ab
abb
abbb
aa
aab
aabb
aaa
aaab
aaabb

aこれは、 an の後に少なくとも 1 つa、または a のb後に 0 個以上bの sが続くように見えます。または単に 2 つ以上の一連bのです。

a(a+|b)b*|b{2,}

a2 つ以上のの連続、または 2 つ以上のの連続、またはの後にが続くb一連ののいずれかであるとも言えます。その表現を書き留めるつもりはありません。ab

結局のところ、これは宿題なので、これを脱糖して最初の結果と組み合わせるのはあなたに任せます。(ところで: 私が使用したすべてのショートカットは単なる構文糖衣であり、正規表現をより強力にするものではありません。つまり、標準の正規表現に変換する単純な構文変換があります。)

[自分が正しいことを願っており、自分を馬鹿にしないでください :-)]

2 に答える 2