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，但是，在class，我的教授举了一个例子，L2 = {a^n b^n | n < 10^10^10 } 并说，这不是正则...

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

谁能说清楚，不胜感激。非常感谢，提前。

Answer 1

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

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

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

Are L1 = {a^n b^n | n < 4 } and L2 = {a^n b^n | n < 10^10^10 }, regular languages?

computer-science

regular-language

fsm