regex - 证明某种语言规则

Question

在我的计算理论课上，我们有一项作业证明语言是规律的。
语言定义为:

B = {1ky | y is in {0, 1}* and y contains at least k 1s, for k >= 1}

在我看来，这种语言似乎需要自动下推才能为此创建机器，但是如果有人可以按正确的方向插入我尝试证明这是一种常规语言。向我展示这些方法之一来证明这一点:创建NFA，DFA，正则表达式或正则语法会有所帮助。

Answer 1

语言L:

L = {1ky | y is in {0, 1}* and y contains at least k number of 1, for k >= 1}

是一种普通语言。确实，这种语言非常简单。 L的简单英文描述是:“所有字符串的集合都由 '0'和 '1'组成，并具有以下限制:每个字符串均以 '1'开头，并且至少包含两个 '1'”。

有问题的语言描述故意使问题变得棘手。解决此类问题的简单方法是:阅读语言尝试理解语言中的字符串模式。尝试写所有可能的最小字符串，然后写第二个最小字符串，依此类推...
另外，请尝试查找不属于该语言的最小长度的字符串。下面，我用您的示例展示了用英语描述编写RE或FA的方法。

让我们在最初的几个步骤中尝试了解语言L允许使用哪种字符串。请阅读以下几点:

语言L中的所有字符串均由'0'和'1'组成

根据1ky和k >= 1，语言L中的所有字符串都必须以'1'开头，因为k大于0。

语言字符串的模式是11...y(或者我们可以说1+y)。为了进一步说明，字符串以一些1开头，后缀y，其中y可以是零个0和一个1的任意子字符串。
注意:因为k可以是大于0的任何数字，所以只有一个简单的约束，即在子字符串y之前必须至少有一个'1'。在第一个'1'之后，您可以考虑将保留后缀作为子字符串y的一部分。

换句话说，我们也可以解释语言L = { 1y, where y contains at least a 1}

现在，正如我所说的，尝试用语言编写一些示例字符串:

一些最小的字符串可以是:

'11'   where k = 1 and y = '1' 
'101'  where k = 1 and y = '01'  
'110'  where k = 1 and y = '10'

另外一个示例:

'111'  where k = 1 and y = 11 #remember in `y` there must be atleat k ones

还有一个示例'1111'，现在可以是k和y吗？字符串'1111'可以通过以下方式进行解释:

'1111'  with k = 1 and y = 111 #remember in `y` there must be atleat k ones
        or   k = 2 and y = 11  #remember in `y` there must be atleat k ones

一些非语言的示例字符串:

不能在L中的字符串是'0'，'00'，'01111'，因为字符串必须以'1'开头。因此，所有模式为0(0 + 1)*的字符串都以'0'开头不是语言。

还有其他可能的字符串，它们以'1'开头，但仍未使用语言。例如'10'是因为如果k = 1(k的最小值)，那么y是'0'。出于同样的原因，string = '1'不是语言。因此，所有带有10*模式的字符串，即'1'，后跟任意数量的零'0'，这不是语言。

因此，所有语言字符串都以'1'开头，并且y部分也至少包含'1'。对于y并没有限制，可以在其中显示'1'。子串y可以是任何零和零的字符串，其中至少有一个单一个，并且y的正则表达式为:0*1(1 + 0)*。

L的正则表达式为:10*1(1 + 0)*
现在，类似的方法可能有助于编写DFA语言，可以引用answer @ drawing minmal DFA for the given regular expression并编写常规语法读取的answer @ Left-Linear and Right-Linear Grammars。