質問

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.

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top