这种语言是否是常规语言?
-
21-12-2019 - |
题
我在字母表 {0,1} 上有语言 {4^(w⋅g)34^(g)|w,g∈NAT}。
我需要查明这种语言是否是可识别的、可判定的、上下文无关的、常规的或都不是。
我该如何去做或知道?
谢谢
解决方案
考虑以下形式的任何字符串 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 定理或泵引理,从假设语言是正则的出发推导出矛盾。
假设您的语言不是上下文无关的。您可以使用上下文无关语言的泵引理,从假设该语言是上下文无关的中导出矛盾。
当然,如果您的语言不可判定或不可识别,您也可以通过各种方式证明这一点。
不隶属于 StackOverflow