regular-language - infinite regular language and finite regular language proof

Question

Suppose L is an infinite regular language. Does it follow that there exists a finite language S such that L = SS* ? Prove or disprove by finding a counterexample.

What i have tried: Intuitively this should be true. Any infinite language can be represented by a finite language S if S has the same alphabets as L e.g if L is the infinite language over the alphabet {a, b}* then S = {a, b} works, so essentially S contains just one occurrence of all the alphabets in L. Is this correct or am i missing something fundamental? or is this just not valid at all?

Any help would be appreciated!

标签： regular-languagefinite-automata

Answer 1

我对此的直觉是，这不是真的。让我们以所有奇长字符串的语言为例{a, b}。这是微不足道的规则，微不足道的无限。L = SS*但是，该语言的任何有限子集都将具有奇数长度的字符串，并且任何无限后缀都必须具有偶数长度，因此对于某些有限语言没有合理的构造S。

我将把这种直觉变成正式的证明给读者。