任何人都可以帮助弄清楚 L = { a m b n , m ≥ n + 2, m ≤ 3 } 是规则的还是不使用泵引理，这似乎有点难以证明。
我曾尝试使用抽引引理，它表明它是常规语言，但我真的很困惑这是对还是错。
问问题
1447 次
2 回答
3
我曾尝试使用抽引引理，它表明它是常规语言，但我真的很困惑这是对还是错。
首先注意，抽水引理可用于证明“某种语言不是常规语言”。但是我们不能用抽引理来证明“某种语言是正则的”。
是的，常规语言的抽引引理描述了所有常规语言的基本属性，如果一种语言不满足抽引引理所描述的条件，或者说不满足抽引引理属性，那么该语言实际上不是常规语言，但是反过来说是不对的！！&mdash- 有“满足引理条件的语言并且可能仍然是非常规的”，意思是：-
抽引引理是语言正常的“必要但不是充分条件”。
这就像：每个工程师都是数学学生 - 所以如果学生是工程师，我们可以说他知道数学，但他们是数学学生，他们不知道工程。（只是给你一个例子来解释）
从您的问题来看，我的印象是您基本上不明白- “什么是常规语言？” .
与常规语言的引理不同，我们需要学习常规语言的一些其他特征——在语言证明中找到它们以证明该语言是常规语言。如果您可以使用有限自动机或/和正则表达式来表示语言，以证明该语言是常规语言。
现在，回到你原来的问题：
如何证明语言 { a m b n , m ≥ n + 2, m ≤ 3 } 是否正规？
因为 'm' 或 'n' 都不能是负数（没有任何符号出现的字符串是可能的，例如空字符串1，但语言符号出现负数的字符串是不可能的）并且根据条件 "m ≥ n + 2", 'm' 总是大于 'n' — 所以 'm' 的最小值（当 'n' 为 0 时）是 2。从第二个条件 "m ≤ 3" 开始，'m' 的最大值是 '3 '，所以 'm' 可以是 2 或 3。
如果你再次注意到第一个条件： "m ≥ n + 2" for m = {2, 3} 'n' 的可能值可以是：
- 对于 m = 2，n 可以为 0，这使得字符串 'aa'。
- 对于 m = 3，n 可以是 0 或 1，这使得字符串 'aaa'、'aaab'。
因此，语言是有限语言 e。仅由三个字符串组成。每一种有限语言都是正则语言，查看维恩图：
（更多地了解这个阅读：正则语言的有限性）
您的语言 L = { a m b n , m ≥ n + 2, m ≤ 3 }的正则表达式将是aa(a + Λ)(b + Λ)，因此证明语言是正则语言。
1没有出现任何符号的字符串在形式语言中称为空字符串或空字符串，在大多数形式语言书籍中符号Ɛ表示空字符串。
Λ 是空符号。
于 2015-03-29T06:15:49.590 回答
-1
我们不能使用抽水引理来证明语言是正则的。要证明一种语言是正则的，我们应该为该语言设计 DFA
于 2015-04-28T15:42:22.623 回答