证明某种语言是正常的

Question

在我的计算理论课中,我们有一个证明语言是常规的任务.该语言定义为:

B = { | 在与含有至少 1秒,对}1kyy{0, 1}*ykk >= 1

这种语言在我看来就像需要一个下推自动机来为此创建一台机器,但是如果有人能够推动我朝着正确的方向努力来证明这是一种常规语言.向我展示其中一种证明方法:创建NFA,DFA,正则表达式或常规语法会很有帮助.

Answer 1

语言L:

L = { | 是在与包含至少一些对}1kyy{0, 1}*yk1,k >= 1

是一种常规语言.确实,这种语言非常简单.L的简单英文描述是:"所有字符串的集合由'0's和 '1's组成,其限制是:每个字符串以'1'并且至少包含两个字符串'1'".

有问题的语言描述被有目的地收集,使问题变得棘手.解决这类问题的简单方法是:阅读语言尝试理解语言中的字符串模式.尝试编写所有可能的最小字符串,然后编写第二个最小的字符串,依此类推......
另外,尝试查找那些不属于该语言的最小长度字符串.下面我展示了我的方法,用你的例子来写英文描述中的RE或FA.

让我们在前几个步骤中尝试理解语言L中允许使用哪种字符串.阅读以下几点:

1. 语言L中的所有字符串都由'0'和 组成'1'
2. 据和在语言L的所有字符串必须下手为是刨丝器比0. 1kyk >= 1 '1'k
3. 语言字符串的模式是11...y(或者我们可以说).为了进一步解释,字符串以一些s 开头,并且有后缀,其中可以是零和s的任意子串. 注意:因为可以是大于0的任何数字,所以只有一个简单的约束,即在子字符串之前 必须至少有一个.首先,您可以将后缀视为子字符串的一部分. 1+y1yy01
ky'1''1'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和y什么？string '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
   

一些不在语言中的示例字符串:

1. 字符串不能在L为'0','00','01111'因为字符串必须与被启动'1'.因此,所有的字符串模式0(0 + 1)*始于'0'不是语言.

2. 还有其他可能的字符串,'1'但仍然没有语言.例如, '10'因为if k = 1(min值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用于给定的正则表达式,并编写常规语法阅读答案@ Left-Linear和Right-Linear Grammars.