正则表达式和语法自由上下文转换

Question

可以将以下 CFG 转换为 Regex 吗？

有人说这可能是正则表达式：(ab* a + b)*

这是真的吗？为什么？看不懂

Answer 1

这不是常规语言。

考虑恰好有一个 b 的语言子集。 （换句话说，语言与 a*ba* 的交集。）如果语言是正则的，则该子集也将是正则的，因为它将是两种正则语言的交集。

但它不是规则的，因为它由字符串组成，其中 b 之后的 a 的数量至少与 a 之前的数量一样大b，那不是正则语言（“正则语言不能算”）。