formal-languages - 是否有任何语言使得它们是彼此的真子集并满足这些条件

Question

有没有这样的语言 A ⊂ B ⊂ C

标签： formal-languages

Answer 1

首先在 {a,b} 上采用非上下文无关语言 A。例如 A = { ww | w \in {a,b}*}，但任何其他的也可以。

然后，您可以在此基础上构建其他语言：

• B = {a,b}* U {a^ic^i | 我 >= 0}
• C = {a,b}* U {a,c}*
• D = {a,b}* U {a,c}* U {b^ic^i | 我>= 0}
• E = {a,b}* U {a,c}* U {b,c}*

然后，您可以验证它们中的每一个是否具有所需的属性。