可以确定每种常规语言的算法
我怎样才能证明存在一种算法可以确定每个正则语言 L 是否 |L| ≥5
how can I show that there exists an algorithm that can determine for every regular language L, whether or not |L| ≥ 5
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
给出一个算法，证明这样的算法存在：D
请记住，正则语言可以通过正则表达式进行匹配（存在一一对应关系）。现在，查看正则表达式，我们可以计算 | 的数量。和 * 在那里，以确定我们是否有 5 个或更多字符串可以接受。
Give an algorithm, which proves that such algorithms exist :D
Remember that regular languages can be matched by regular expressions (there's a 1-to-1 correspondence). Now, looking at a regular expression, we can count the number of | and * in there, to determine if we have 5 or more strings that will be accepted.
我认为案例分析会有所帮助。例如，如果语言支持以下内容：
下面显示了这些情况下可能的单词数：
现在，如果我们有一个可以确定单词数量的算法，那么所要求的算法就很简单了。
I think case analysis will help. For example, if the language supports the following:
The following shows the number of possible words for the cases:
Now, if we have an algorithm that can determine the number of words, the algorithm asked for is trivial.
这很简单。正则语言是如何生成的？通过 dfa（确定性有限自动机）。
您不仅可以使用 dfa 来检查某个单词是否属于语言 L，还可以使用 L 生成所有单词。这是通过递归遍历图来完成的。 L 可能包含无限个单词，因此遍历算法也会无限运行。但如果你找到了一个单词，你就会增加一个计数器。当你最终达到 5 个单词时，你就打破了它。
It is quite simple. How is a regular language generated? By an dfa (deterministic finite automate).
You can use dfa not just for checking if a word is in a language L but also for generate all words from L. This is done by traversing the graph recursive. Potenially L can contain infinite words so the traversing algorithm runs also endlessly. But in case you found a word you increment a counter. And when you finally reach your 5 words you break it.