正規言語から正規表現を導出します

Question

以下の言語を考えると、私は言語の正規表現を見つけるのですか。

L = {^ N B ^ M | N => 1、M => 1、NM => 3}

Answer 1

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 {^ N B ^ M | N> = 2、M> = 2}

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

（（ABBB（B *））|（AAA（*）b）の|（AA（*）BB（B *）））

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

Answer 2

言語の例の単語の集合を書き留めます。それらの感触を取得します。パターンを探してください。共通接頭辞/接尾辞/部分文字列を探します。

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又はおそらくはゼロ以上as続いbのいずれかに続いbのいずれかのように見えます。あるいは単につ以上のbs一連ます。

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

また、それは、少なくとも二つのasのシリーズまたは少なくとも2 bsのシリーズまたはas続くbs一連のどちらかであると言えるでしょう。私はその式を書き留めるつもりはありません。

私はこれをdesugarし、最初の結果と一緒にそれを置くためにあなたにそれを残しておきますので、

このの、すべての後、の宿題です。 （ところで：私はを使用するすべてのショートカットがちょうど糖衣構文のであり、彼らはのの正規表現をより強力にしていないすなわちは、単純な構文の変換は、標準的な正規表現になり、それらことがあります。 。）

[私はちょうど私が正しい希望と自分のお尻をしない： - ）]