CODEWITHSUNDEEP
regular-languagefinite-automata
Johm
Johm

Reputation: 11

infinite regular language and finite regular language proof

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!

Upvotes: 1

Views: 806

Answers (2)

Patrick87
Patrick87

Reputation: 28312

Here's an alternative counterexample that might be easier. Consider the infinite regular language ab*. Now suppose L = SS* for some S. Now, either S contains a string with a in it, or it does not. If it does, then L = SS* contains strings with multiple a's, so it cannot be the language ab*. If S does not contain a, then L = SS* contains no strings with any a's at all, and can't be the language ab*. In either case, L is not ab*, a contradiction. So L cannot be written as SS* for any S.

Upvotes: 0

Welbog
Welbog

Reputation: 60448

My intuition on this is that it's not true. Let's take the example of the language of all odd-length strings over {a, b}. This is trivially regular, and trivially infinite. However, any finite subset of this language will have odd-length strings, and any infinite suffix would have to have an even length, so there is no reasonable construction of L = SS* for some finite language S.

I'll leave turning this intuition into a formal proof to the reader.

Upvotes: 0

Related Questions