# Example of non-regular context free language L such that prefix(L) is regular

Suppose we have some non-regular context free language L. Suppose we also have language of all prefixes of words in L.

What can be an example of non-regular language L such that language of it's prefixes is regular (Can be represented by a finite automaton)?

I don't understand how language of prefixes can ever be regular, since the set of prefixes of a word include the word itself.

For example $$L= a^nb^n$$ is my non-regular language. The language of it's prefixes would include : $$\epsilon,a^n$$ where $$n\ge 1$$,$$a^nb$$ where $$n\ge 1$$ etc...

But what about b's ? We need to know how many a's there were in the first place. Therefore I don't see how the language of prefixes can be regular.

## 1 Answer

Consider the language of words with the same number of a's and b's. It is non-regular but the set of prefixes is the set of all words which clearly is regular.

• Thanks that's super helpful ! Nov 14, 2019 at 0:08