[Solved]: Proving $A$ avoiding $B$ regular if $A$ and $B$ are regular

Problem Detail: 

Suppose we define an operation such that

$$A \text{ avoiding } B = \{w \in A \mid w\text{ has no substring in }B\}\,.$$

How can I prove that, if $A$ and $B$ are regular then $A\text{ avoiding }B$ is regular too? I know I should either construct a DFA/NFA or use closure properties, but where to start?

What I come up with is that $A = (A\text{ avoiding } B) \cup \{w \mid w\text{ has a substring in }B\}$ and then I've tried to prove that $\{w \mid w \text{ has a substring in }B\}$ is regular by constructing a DFA for it. That would show that $A \text{ avoiding } B$ is also regular.

Asked By : Dr.Pro

Answered By : Shreesh

Yes you are on right track.

We can first define ($A$ avoids $B$) as ($A$ - ($A$ has $B$)), where ($A$ has $B$) are strings of $A$ which contain strings of $B$ as substrings. Then ($A$ avoids $B$) will be strings of $A$ that do not contain strings of $B$ as substrings.

We can define ($A$ has $B$) as $A \cap (\Sigma^* B \Sigma^*)$. Then ($A$ has $B$) are strings of $A$ which contain strings of $B$ as substrings.

Thus you have ($A$ avoids $B$) = ($A - (A \cap (\Sigma^* B \Sigma^*))$). Since regular languages are closed under concatenation, intersection, and subtraction they are also closed under operaion avoid.

Above relation also gives ($A$ avoids $B$) = $A - \Sigma^* B \Sigma^*$ as pointed out by Hendrik Jan.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53034