CODEWITHSUNDEEP
regular-languagedfanfaautomaton
user76508
user76508

Reputation: 267

If pref(L) is regular, does that imply L is also regular?

I have this exercise for homework:

Say we have a language L. we know that the language pref(L) (all the prefixes of L, including all the words in L itself) is a regular language. Does this imply that the language L is regular as well?

I took the NFA of pref(L) and divided it (via 2 epsilon transitions from q0) to 2 separate NFA's, as 1 defines L and the other defines pref(L)\L.

What I actually got is a NFA for L, which means it is regular.

I am not sure this is the way or if it legal. I'd be glad for another lead.

Thanks in advance,

Yaron.

Upvotes: 1

Views: 1770

Answers (1)

templatetypedef
templatetypedef

Reputation: 372784

It is not necessarily the case that if pref(L) is regular, then L is regular as well.

As an example, let Σ = {a} be a unary alphabet. I'm going to claim that if L is any infinite language over Σ, then pref(L) = Σ*. To see this, first note that pref(L) ⊆ Σ* because every pref(L) is a language over Σ. Now, consider any string in Σ*, which must have the form an. If L is an infinite language over Σ, it must contain at least one string of the form am where m ≥ n. Then an would be a prefix of am, so an ∈ pref(L). This shows that Σ* ⊆ pref(L) and that pref(L) ⊆ Σ*, so in this case Σ* = pref(L).

Now, all we need to do is find a nonregular language over Σ = {a}. As an example, take the language { a2n | n ∈ N } of all strings whose length is a power of two. It's possible to prove using either the Myhill-Nerode theorem or the pumping lemma that this language is not regular. However, by the above result, we know that pref(L) is a regular language.

Hope this helps!

Upvotes: 2

Related Questions