regular-language - 正则语言的有限性

Question

我们都知道(a + b)*是仅包含符号的常规语言 a和 b .
但是(a + b)*是一个无限长的字符串，它是有规律的，因为我们可以建立一个有限自动机，所以它应该是有限的。

任何人都可以解释一下吗？

Answer 1

可以为任何正则语言构造有限自动机，正则语言可以是有限集或无限集。当然，有无限集合那些不是常规集合。检查下面的维恩图:

_{Notes:
     1. every finite set is a regular set.
     2. any dfa for an infinite set will always contains loop (or dfa without loop is not possible for infinite set).
     3. every non-regular language is an infinite set.}

有限自动机中的“有限”一词意味着在自动机中存在“有限数量的内存”，用于常规语言类，因此在处理时的任何时间实例中只能存储“有限”(或称有界)信息量一串语言。

在有限自动机中，内存仅以状态的形式存在(而在另一类自动机中，如 Pda，图灵机的外部内存用于存储无界信息)。您可以将有限自动机视为没有显式内存的 CPU；只能在其寄存器中存储最近的结果。

因此，我们可以将“常规语言”定义为——一类在处理语言字符串时只需要在任何时间存储有限(有限)信息的语言。

进一步阅读(对于无限语言):

什么是正则语言:What is basically a regular language? And Why a*b* is regular? But language { anbn | n > 0 } is not a regular language

要了解状态如何用作内存元素，请阅读以下答案:How to write regular expression for a DFA

有限和无限正则语言的自动化之间的区别:To make sure: Pumping lemma for infinite regular languages only?