什么是语言类型

Question

{xwx|x€{a,b}+,w€{a,b}+}

是常规还是CFG？在我看来，我可以把它写成(a+b)(a+b)+(a+b)。所以它应该是常规的，但我不确定。

Answer 1

就像捅说的那样，这种语言不能正常，因为x出现两次。它是一种无上下文的语言，因为下推自动机可以通过在第一个x中推送a和b并将它们弹出第二个x来接受它。无上下文语言的经典示例是Dyck language，它由具有正确嵌套括号的字符串组成。你的两个表达方式也不相同也是对的。