regular-language - 这种语言是否正规？

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 定理或抽水引理，以从假设语言是常规语言中推导出矛盾。

假设您的语言不是上下文无关的。您可以将抽水引理用于上下文无关语言，以从假设语言是上下文无关的情况下得出矛盾。

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