3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)$?

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Saad Oct 13 '17 at 14:36
  • 1
    $\begingroup$ You asked for a hint - I gave you a hint. $\endgroup$ – Yuval Filmus Oct 13 '17 at 14:38
  • $\begingroup$ 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. $\endgroup$ – Saad Oct 13 '17 at 14:41
  • $\begingroup$ As a further hint, the answer to my question is "Yes". $\endgroup$ – Yuval Filmus Oct 13 '17 at 14:42
  • 1
    $\begingroup$ Don't expect it to hit home immediately. Solving math exercises often takes time. $\endgroup$ – Yuval Filmus Oct 13 '17 at 14:42
1
$\begingroup$

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.

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

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