是否有任何技巧可以通过仅查看语言来猜测语言是否是常规语言?
为了选择证明方法,首先我必须有一些假设。您是否知道在解决长问题时减少时间消耗所需的任何提示/模式?
例如,为了不花时间在引理上,当语言是规则的并且我不想构造 DFA/语法时。
例如:
1. L={w ε {a,b}*/no of a in (w) < no of b in (w)}
2. L={a^nb^m/n,m>=0}
只看上面的例子,如何判断哪个是常规的?
是否有任何技巧可以通过仅查看语言来猜测语言是否是常规语言?
为了选择证明方法,首先我必须有一些假设。您是否知道在解决长问题时减少时间消耗所需的任何提示/模式?
例如,为了不花时间在引理上,当语言是规则的并且我不想构造 DFA/语法时。
例如:
1. L={w ε {a,b}*/no of a in (w) < no of b in (w)}
2. L={a^nb^m/n,m>=0}
只看上面的例子,如何判断哪个是常规的?
通常,在查看一种语言时,判断该语言是否规则的一个好的经验法则是考虑一个可以读取字符串并回答“该字符串是否属于该语言?”问题的程序。
要编写这样的程序,您是否需要在变量中存储一些任意值,或者程序的状态(即所有可能变量值的组合)是否仅限于一些有限的固定数量的可能性?如果该语言可以被只需要固定数量的变量且只能具有固定数量的值的程序识别,那么您就有了常规语言。如果不是,那就不是。
使用这个,我可以看到第一种语言不是常规的,但第二种语言是。在第一语言中,我需要记住a
我见过多少 s,以及多少b
s。(或者至少,我需要跟踪 (# of a
s) - (# of b
s),并在该计数为负时接受字符串是否结束)。同时,a
s 的数量没有限制,所以这个计数可以任意大。
在第二语言中,我根本不在乎什么n
和m
是什么。因此,对于第二种语言,我的程序只会跟踪“我至少看过一种b
吗?” 确保我们没有a
出现在第一个之后的任何字符b
。(所以,一个变量只有两个值——真或假)
因此,将语言 1 变为常规语言的一种方法是将其更改为:
1. L={w ∈ {a,b}*/no of a in (w) < no of b in (w), and no of a in (w) < 100}
现在我不需要跟踪a
我在达到 100 后看到的 s 的数量(从那时起我自动知道该字符串不在该语言中),同样还有b
s 的数量 - 一旦我达到 100,我可以停止计数,因为我知道这已经足够了,除非a
s 的数量本身太大。
您应该注意的一个常见情况是,当有人问您有关“ a
s 的数量是 13 的倍数”或“ w ∈ {0,1}* 并且w是 13 的倍数的二进制表示”的语言时. 有了这些,您似乎需要跟踪整个数字来做出决定,但实际上您不需要 - 在这两种情况下,您只需要保留一个可以从 0 计数到 12 的变量。所以请注意用于“多种”类型的语言。(以及相关的“奇数”或“偶数”或“比13的倍数多1”)
但是,其他数学属性——例如,w ∈ {0,1}* 和w是完美正方形的二进制表示——将导致非常规语言。