regular-language - 我怎样才能直接看到一种语言不规则

Question

给定 L={a^nb^nc^n}，我怎么能直接说这种语言不规则而不看生产规则？我可以使用抽引引理，但有些人说只是看语法，这不是常规的。这怎么可能？

Answer 1

你的字母表中有三个字符。它们都依赖于同一个变量：n。现在，如果你只有两个，想象一下 {a^nb^n} 你可以用这个产生式轻松完成任务：

S -> ab | 锑

但是你有三个，没有办法将它们都链接到同一个变量。您应该使用两个语法类别，但既然您这样做了，它们就会被取消链接，您可以从它们中的每一个生成不同的字符串。链接它们的唯一方法是只使用一个语法类别，这是不可能的。

你不能这样做：

S -> abc | aSbc

实际上，您的最终字符串中不能有语法类别，因此这不是字符串。它需要再次转变。从那时起你能做什么？你可以做：

美国广播公司

或者你可以这样做：

aaSbcbc

第一个是字符串，不属于您的语言。第二个还不是字符串。但是很容易看出您无法从中执行任何允许的字符串。