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$

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.

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.