Proving that $B(L)$ is regular if $L$ is regular

35 Views Asked by At

$L$ is a binary language.

$$B(L) = \{ w | w ∈ L \text{ and }|w|>10 \}$$

I need to prove the following:

If $L$ is regular $\rightarrow$ $B(L)$ is regular

I thought about doing it using Nerode's theorem:

We know that $L$ has a finite number of equivalence classes (let's call it $N$).

Every word in $B(L)$ is also in $L$ with the condition that it's longer than $10$.

so can I say that the number of equivalence classes in $B(L)$ is at most $N+11$ because we're only adding classes that are distinguishable by whether or not $wz$ adds up to $11$ or not. (in the case that all words in $L$ are already greater than $10$ - the number of equivalence classes in $B(L)$ is also $N$)

Therefore, $B(L)$ has a finite number of equivalence classes $\rightarrow$ $B(L)$ is regular?

1

There are 1 best solutions below

1
On BEST ANSWER

It actually is $11N + 1$, because for each class we originally had, we potentially need to distinguish cases when length of word is $1, 2, \ldots, 10$ or more from this class, and possibly move empty word to it's own class, but otherwise it's correct.

However I think Myhill–Nerode is an overkill here: all you need is that intersection of two regular languages is regular and the fact that language consisting of words with length greater than $10$ is regular.