computer-science - L1 = {a^n b^n | n < 4 } 和 L2 = {a^n b^n | n < 10^10^10 }，常规语言？

Question

是 L1 = {a^n b^n | n < 4}，一种常规语言？

在我看来，它是有规律的，因为我可以为它画一个FSA，但是，在类里面，我的教授举了一个例子，L2 = {a^n b^n | n < 10^10^10 } 并说，这不是正则...

所以，我的问题是，如果我可以为 L1 绘制 fsa，我什至可以为 L2 绘制...为什么 prof.说，这不是正规的吗？因为，L1 和 L2 这两种语言都是有限的......我刚刚自己学习了 L1 语言来思考这个问题......类里面没有讨论 L1......另外，我读过，所有有限语言都是规则的……所以在我看来，这两种语言都应该是……:)

如果有人能解释清楚，我将不胜感激。非常感谢，提前。

Answer 1

每一种具有有限数量字符串的语言都是规则的。所以 L1 和 L2 都是正则的。因为如果一种语言具有有限数量的字符串，我们可以构造以下 NFA，其中 ε 表示空转换:

 ------ first string
|      
ε
|
 ------ second string
|
ε
|
 ------ ...
|
.
.
.
|
 ------ last string