我最近开始学习形式语言理论,并在有限和无限语言方面遇到了一些问题。
有人告诉我,所有有限语言都是规则的。
然而,通读给我的笔记,一个带有产生式的语法:
S --> ab
S --> aabb
S --> aaabbb
尽管产生的字符串数量有限,但它不是常规语言。
但是,产生式的语法:
S --> Sb
S --> Tb
T --> Ta
T --> a
它生成 a^mb^n 形式的字符串,这是一个无限的字符串列表,但这种语言被定义为常规语言?
谁能帮我简单理解一下?在我苦苦挣扎时将不胜感激。