Is this language regular

Question

Given R a regular language.

Is the following language also regular:

Comp(R) = { u | u is NOT a sub-word of a word in R }

It looks like there are no words in Comp(R) since there can not be any sub-word of word in R. But I might get it wrong. any suggestions?

Answer 1

The two following theorems implies that the answer is yes:

• The complement of a regular langage is regular: see Why is the complement of a regular language still a regular language?
• The language of all the subword of a regulare langage is regular (double all transitions by epsilon transitions)