Problem Detail: Suppose we define an operation such that $$A text{ avoiding } B = {w in A mid wtext{ has no substring in }B},.$$ How can I prove that, if $A$ and $B$ are regular then $Atext{ 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 = (Atext{ avoiding } B) cup {w mid wtext{ 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
