我怎么能说一见语言没有上下文？

Question

我的教授希望我们能够快速判断一个给定的语言是否是常规的,无上下文但不是常规的,或者不是无上下文的(换句话说,没有绘制PDA,编写无上下文语法,并使用泵浦引理进行上下文 - 免费语言).

我知道一些技巧可以帮助我们快速讲述乍一看常用语言的内容,而不是语言是否无上下文.

谢谢.

Answer 1

当然,没有普遍的答案.但是有一些一般模式,CF可以或不可以以不同的变体出现.CF可以做的事情(而不是REG):

• 同时在两个地方计数,比如在^ nb ^ n,
• 也反复喜欢在^ nb ^ na ^ mb ^ m
• 或嵌套在^ nb ^ ma ^ mb ^ n中
• 回文模式,即w后跟w的反向
• 计算一个字母与另一个字母的数量,例如"a和b的数量相等的单词"或"b比b多5的单词"

CF不能做的典型事情:

• 在三个地方同时计数,例如在^ nb ^ nc ^ n中
• 在两个交叉对的位置同时计数两次,例如在^ nb ^ ma ^ nb ^ m中
• 像ww这样的两个有序副本
• 比较三个字母的数字,如"a,b和c相等的单词".

考虑到这些模式,您应该能够确定大多数常见示例语言的上下文无关性.