简化正则表达式，自动机理论
Simplify Regular Expression, Automata Theory
我最近需要找出该语言的正则表达式
{w | |w|是奇数，w 以字母表 {a,b} 中的符号 b} 开始和结束。
我想出了一个解决方案
b(ab+bb+aaab+aabb+abab+abbb+bbbb+bbab+babb+baab)*
解决方案很长，所以我希望有人能告诉我一个可以简化的方法，
你可以试试b|(b(a|b)((a|b)(a|b))*b)
您描述的语言只能生成 b，它被第一个分支捕获，这是它可以生成的唯一大小为 1 的字符串。然后它可以产生大小为 3,5,7,... 的字符串。那些被第二个分支捕获。开头和结尾的 b 是不言自明的。那些占2个字符。中间位是 {w | |w| is odd} over {a,b}.
的经典语言
更强大的语法将允许像 b((a|b)((a|b)^2)*b)? 这样的东西，它更紧凑，但等效。
最简单的一个：
(b(a|b)(aa|ab|ba|bb)*b)|b
我最近需要找出该语言的正则表达式 {w | |w|是奇数，w 以字母表 {a,b} 中的符号 b} 开始和结束。
我想出了一个解决方案
b(ab+bb+aaab+aabb+abab+abbb+bbbb+bbab+babb+baab)*
解决方案很长，所以我希望有人能告诉我一个可以简化的方法，
你可以试试b|(b(a|b)((a|b)(a|b))*b)
您描述的语言只能生成 b，它被第一个分支捕获，这是它可以生成的唯一大小为 1 的字符串。然后它可以产生大小为 3,5,7,... 的字符串。那些被第二个分支捕获。开头和结尾的 b 是不言自明的。那些占2个字符。中间位是 {w | |w| is odd} over {a,b}.
更强大的语法将允许像 b((a|b)((a|b)^2)*b)? 这样的东西，它更紧凑，但等效。
最简单的一个：
(b(a|b)(aa|ab|ba|bb)*b)|b