regex - 这是普通语言吗？如果是这样，它的正则表达式是什么？

Question

B = {1^k y | k >= 1, y in {0, 1}* and y contains at least k 1's }

这种语言是正规的吗？如果是这样，你如何证明它，你将如何用 Python 中的正则表达式来表示它？

这是课堂作业，所以如果您能解释答案背后的原因和过程，将不胜感激。

Answer 1

您拥有的语言相当于这种语言：

B' = {1 y | y in {0, 1}* and y contains at least one 1}

您可以证明 B' 是 B 的子集，因为 B' 中的条件与 B 相同，但 k 设置为 1。

证明 B 是 B' 的子集涉及证明 B 中 k >= 1 的所有单词也属于 B'，这很容易，因为我们可以去掉 B 中所有单词中的前 1 并设置y为其余的字符串，y则将始终包含至少一个 1。

因此，我们可以得出结论B = B'。

---

所以我们的工作被简化为确保第一个字符是 1 并且字符串的其余部分至少有 1 1。

正则表达式（CS 表示法）将是：

10*1(0 + 1)*

在常见的正则表达式引擎使用的符号中：

10*1[01]*

外交部：

这q2是一个最终状态。

“至少”是解决这个问题的关键。如果这个词变成“平等”，那么故事就会不同。