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?

Yes Regular, you can - draw DFA for Comp(R) as: **Step-1)** mark all stats as final state in DFA of R, **Step-2)** [find complement DFA](http://stackoverflow.com/questions/14802732/finding-the-complement-of-a-dfa/14817545#14817545) — Grijesh Chauhan, Feb 01 '14 at 09:06
*`It looks like there are no words in Comp(R) since there can not be any sub-word of word in R`* ?? what do you means by sub-words in R? — Grijesh Chauhan, Feb 01 '14 at 09:13
Rouki Re-writing steps: (assuming you don't have dead states in DFA of R, and this is always possible) **step-1)** mark all stats as final states **step-2)** mark all states as initial states (not you got an NFA) **step-3)** Convert NFA into DFA **step-4)** Complement new DFA -- you will get DFA for comp(R)!! — Grijesh Chauhan, Feb 01 '14 at 09:23

score 1 · Answer 1 · edited May 23 '17 at 12:03

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)

edited May 23 '17 at 12:03

Community

answered Feb 01 '14 at 09:13

hivert

I difficulty is OP saying `any sub-word`, but not all possible prefixes.. that the reason I didn't posted an answer. but +1 as indeed it is a regular. – Grijesh Chauhan Feb 01 '14 at 09:19

1 Answers1