证明某种语言正则

在我的计算理论课上，我们的作业是证明一种语言是正规的。 该语言定义为：

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

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

语言L：

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

是一种常规语言。事实上，这种语言非常简单。 L 的简单英文描述是：“所有字符串的集合包含'0's and '1's 的限制是：每个字符串都以'1'并且还包含至少两个'1'".

问题中给出的语言描述是故意复杂化的，以使问题变得棘手。解决此类问题的简单方法是：阅读语言并尝试理解语言中的字符串模式。尝试写出所有可能的内容smallest字符串，然后写入第二小的字符串，依此类推......
另外，尝试找到最小长度的字符串doesn't属于语言。下面我用你的例子展示了我从英文描述中编写 RE 或 FA 的方法。

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

1. 语言 L 中的所有字符串均由以下组成'0' and '1'
2. According to 1ky and k >= 1, all strings in language L must start with '1' as k is grater than 0.
3. Pattern of language strings is 11...y (or we can say 1+y). To explain further, string start with some ones 1s, and has suffix y, where y can be any arbitrary sub string of zeros 0s and ones 1s.
   Note: Because k can be any number greater than 0, there is just a simple constraint that before sub-string y there must be at least one '1'. After first '1' you can consider remain suffix as a part of sub-string y.
4. 换句话说，我们也可以解释语言L = { 1y, where y contains at least a 1}

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

1. 一些可能的最小字符串可以是：

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

2. 再举一个例子：

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

3. 再举一个例子'1111'，现在可以怎样k and 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
   

一些示例字符串是not语言：

1. 不能出现在 L are 中的字符串'0', '00', '01111'因为字符串必须以'1'。所以所有字符串都带有模式0(0 + 1)*以。。开始'0'不在语言中。

2. 还有其他可能的字符串以'1'但仍然不是语言。例如'10'因为如果k = 1（最小值k) then y is '0'。出于同样的原因，字符串='1'不是语言。所以所有带有模式的字符串10*那是'1'后跟任意数量的零'0'不是语言。

所以语言中的所有字符串都以'1' and y部分还至少包含一个'1'。没有限制y那个地方'1'可以出现。子串y可以是任何由 0 和 1 组成的字符串，并且至少有一个 1 和正则表达式y is: 0*1(1 + 0)*.

L 的正则表达式为：10*1(1 + 0)*

现在，类似的方法有助于为语言编写 DFA，可以参考答案@为给定的正则表达式绘制最小 DFA https://stackoverflow.com/a/14024179/1673391并编写常规语法阅读答案@左线性和右线性文法 https://stackoverflow.com/a/13945932/1673391。