regex - 从正则语言派生正则表达式

Question

给定下面的语言，我如何找到该语言的正则表达式

L = {a ^nb ^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 { a^nb^m | n>=2,m>=2 }

这个正则表达式应该等同于 L：

((abbb(b*)) | (aaa(a*)b) | (aa(a*)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

这有点像 ana后跟至少一个a或b可能后跟零个或多个bs。或者只是一个多于两个b的系列。

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

您也可以说它是至少两个as 的系列或至少两个bs 的系列或as 后跟bs 的系列。我不会写下那个表达。

毕竟这是作业，所以我将把它留给你去脱糖，然后把它和第一个结果放在一起。（顺便说一句：我使用的所有快捷方式都只是语法糖，它们并没有使正则表达式更强大。即有一个简单的语法转换将它们变成标准正则表达式。）

[I just hope I'm right and don't make an ass of myself :-)]