这是一种常规语言吗？如果是这样,它的正则表达式是什么？

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是最终状态.

"至少"是解决这个问题的关键.如果这个词变得"平等",那么故事将会有所不同.