2
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks that's super helpful ! $\endgroup$ – Mandy Nov 14 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.