这种语言是否是常规语言？

Question

我在字母表 {0,1} 上有语言 {4^(w⋅g)34^(g)|w,g∈NAT}。

我需要查明这种语言是否是可识别的、可判定的、上下文无关的、常规的或都不是。

我该如何去做或知道？

谢谢

Answer 1

考虑以下形式的任何字符串 4^a 3 4^b. 。我们能找到吗 w, g 为了我们的 a, b？嗯，我们知道 g 必须等于 b, ，然后我们可以选择 w = a + g. 。自从 a, b 和 g 是自然数，所以也一定是 w;答案是，是的，对于任何形式的字符串 4^a 3 4^b, ，我们有一个用您的语言表示的字符串。

该形式的所有字符串的语言 4^a 3 4^b 由正则表达式描述 4* 3 4* 因此，你的语言是规则的、上下文无关的、可判定的和可识别的。

假设你的语言不规则；你怎么知道？您可以使用正则语言的 Myhill-Nerode 定理或泵引理，从假设语言是正则的出发推导出矛盾。

假设您的语言不是上下文无关的。您可以使用上下文无关语言的泵引理，从假设该语言是上下文无关的中导出矛盾。

当然，如果您的语言不可判定或不可识别，您也可以通过各种方式证明这一点。