0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What approaches have you tried? Where did you get stuck with them? We want to help you understand concepts, but we don't want to just do your exercise for you. As you haven't given us much to react to, it's hard to know how to help you. Please spend some time trying to solve the problem yourself, then edit the question to show what you've tried and articulate a specific question about some specific aspect that has you confused. You must be able to identify some possible approaches -- so give them a try and see how far you're able to get. $\endgroup$ – D.W. Feb 13 '16 at 4:23
  • $\begingroup$ @D.W. my question is how to start, not ask people to help me do the homework, as I mentioned, I know I should use DFA or closure properties, but just don't know where to start and some hint. $\endgroup$ – Dr.Pro Feb 13 '16 at 4:29
  • $\begingroup$ I'm afraid "Here's my homework exercise, how do I start?" is probably not a good question for this site format and might not be received positively by folks here. We want you to make a significant effort on your own before asking here, and then if you get stuck, to show us what you've already tried and where you got stuck and what your specific issue is. See here for a relevant discussion. If you don't know how to start, try to solve it for a special case, e.g., where B contains only a single string. $\endgroup$ – D.W. Feb 13 '16 at 4:45
  • $\begingroup$ @D.W. like here says, I don't think it's a shame to say this is a homework question, and I do put a lot of efforts into this question, of course including searching the whole site. And I appreciate your advice of asking question, but I don't think it would help me tackle this question. $\endgroup$ – Dr.Pro Feb 13 '16 at 5:25
9
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.