常规语言的有限性

Question

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

有人可以解释一下吗？

Answer 1

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

_{注意:
     1.每个有限集都是常规集.
     2.无限集的任何dfa将始终包含循环(或无循环的dfa对于无限集不可能).
     每一种非常规语言都是无限的.}

有限自动机中的"有限"一词意味着在常规语言类的自动机中存在"有限量的存储器",因此在处理过程中,只有"有限"(或有限的)信息量可以存储在任何时刻.一串语言.

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

因此,我们可以将"常规语言"定义为 - 一类语言,在处理语言字符串时,只需要在任何时刻存储有界(有限)信息.

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

• 什么是常规语言:基本上什么是常规语言？为什么a*b*经常？但语言不是常用语言{ anbn | n > 0 }
• 要了解状态如何用作内存元素,请阅读以下答案:如何为DFA编写正则表达式
• 有限和无限常规语言的自动化之间的区别:确保:仅为无限常规语言提供引理？