正则表达式 – 定期证明某种语言

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,其中y至少包含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,可以参考答案@ drawing minmal DFA for the given regular expression并编写常规语法阅读答案@ Left-Linear and Right-Linear Grammars.