# Proving OP(L) is regular [closed]

I did some searching before I decided to ask this question and there was nothing similar to my question that helped me. So I came to CS stack-exchange for hints. So, I am currently working on a proof to show that if $L$ is regular then $OP(L)$ is also regular without the use of pumping lemma. For the sake of this question, I am using $\{0,1\}$ as alphabet.

$$OP(L) = \{w \mid wz ∉ L \text{ for every } z ∈ \{0,1\}^+ \}.$$

At the moment, I have a hard time starting the proof. What I understand is that, if $L$ is regular then we can define a DFA that can decide $L$. And then we can define another machine for $OP(L)$ with every transition from $M$ along with $\epsilon$-transitions.

Am I on the right track? I could really use some hints.

## closed as off-topic by D.W.♦Oct 23 '17 at 13:57

• This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

• – J.-E. Pin Oct 23 '17 at 10:09
• Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. – D.W. Oct 23 '17 at 13:57
• I'm voting to close this question because it was cross-posted. – D.W. Oct 23 '17 at 13:57

Hint: Consider a DFA for $L$, and some word $w$. Suppose that upon reading $w$, the DFA reaches some state $q$. Is knowing $q$ enough for deciding whether $w \in OP(L)$?

• Can you please elaborate a bit? The way i am thinking about this is that the state q also has to be in the machine for OP(L). – Saad Oct 13 '17 at 14:36
• You asked for a hint - I gave you a hint. – Yuval Filmus Oct 13 '17 at 14:38
• That's true but the hint is not hitting the home yet. If you'd be kind enough and explain it in like 2-3 sentences that'd be much appreciated. – Saad Oct 13 '17 at 14:41
• As a further hint, the answer to my question is "Yes". – Yuval Filmus Oct 13 '17 at 14:42
• Don't expect it to hit home immediately. Solving math exercises often takes time. – Yuval Filmus Oct 13 '17 at 14:42

A possibility is the use closure properties of the regular languages. The new language $\mathrm{OP}(L)$ can be written using concatenation and Boolean operations using the original $L$ and simple regular languages.

• But then that won't be a full proof, would it? – Saad Oct 13 '17 at 15:24
• Why wouldn't it be a full proof? We are allowed to use known results in proofs. – Yuval Filmus Oct 13 '17 at 16:17