这是常用语言吗？如果是这样，那么正则表达式是什么？

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]* 

的DFA：

这里q2是最终状态。

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