I have to prove that if a language $L$ is regular then:

a) $NONPREFIX(L)=\{u \in L / $none of the prefixes (not $\epsilon$ or $u$) of $u$ are elements of $L \} $ is regular

On this one I think I can divide the words of L in two parts and get it, since regular languages are closed under concatenation, I dont know if this is correct.

And the other one:

b) $NONEXTENSION(L)=\{u \in L / $ $u$ is not a prefix (not $\epsilon$ or $u$) of any element of $L \} $ is regular

In this one I've no idea how to begin.

Any help would be pretty apreciated. Thanks!

  • $\begingroup$ Please ask only one question per post. See cs.stackexchange.com/q/1331/755. We discourage "here is my exercise-style task, can you solve it for me" or "here is my exercise-style task, I have no idea how to begin". $\endgroup$
    – D.W.
    Nov 11 '20 at 19:46

a) Proving NOPREFIX(L) is regular :

The idea is simple , for a string w ∈ NOPREFIX(L) , w must be in L , and no proper prefix of w is in L

So , if we have a DFA M for L , we run string w on M , changing M a bit , if M enters the accept state before the end of the input , then a proper prefix of w is accepted by L and so we reject , if not and we reach an accept state just by the end input we accept , of course if by the end of w we don't enter an accept state we reject since w is not in L an so not in NOPREFIX(L)

Now you may want to try constructing M' based on the above explanation , then check your answer

Proof :

Let M = (Q,Σ,δ,q0,F) recognising some regular language L ,construct M' = (Q',Σ,δ',q0',F') to recognise NOPREFIX(L) as follows :

Q' = Q

for r ∈ Q' , a ∈ Σ

δ'(r,a) = δ(r,a) , if r is not in F

δ'(r,a) = ∅ , if r ∈ F

q0' = q0'

F' = F

Hopefully you can see how changes in δ' achieve our purpose , M' simulates M , till it reaches an accept state , if the input ends we accept ( note that w is not a proper prefix of w) since w ∈ L , and we did not encounter any accepted proper prefixes , but if we enter an accept state and the input is not yet finished we reject since this means that we encountered an accepted proper prefix

b) Proving NOEXTEND(L) is regular

This is an easier one , for a string w ∈ NOEXTEND(L) , we need to make sure that no string wx ∈ L , x ∈ Σ^+ , so for w not to be a proper prefix of a string in L ,we need to make sure that no symbols could be added to w to form a string in L ,

Once again you may want to try M' that recognises NOEXTEND(L)

Proof :

Let M = (Q,Σ,δ,q0,F) recognising some regular language L ,construct M' = (Q',Σ,δ',q0',F') to recognise NOEXTEND(L) as follows :

Q' = Q δ' = δ q0' = q0'

F' = { q| there is no path from q to an accept state in F)

M' works exactly as M , when the string end we consider the final state we reached q , if there is a path from q to any accept state in F ( the accept states of M) , then we reject since this means we can extend w by x to reach a string wx ∈ L , with x being the string of symbols on the path from q to accept state , and thus w is a proper prefix of some string wx ∈ L , if there is no path from q to an accept state so w cannot be extended to form a string in L and thus we accept

  • $\begingroup$ Nice, I understand the idea and is pretty nice but still have two issues, if we redefine de transition from the accepting states of M then F' is not equal to F isn't it?, if we have two consecutives accepting states in M then in M' we'll not have the first one. So in my point of view $F'=F \setminus \delta'^{-1}_1(\emptyset)$, I don´t know if I´m wrong (I am referring to the first problem) $\endgroup$
    – Tt Nach00
    Nov 12 '20 at 10:32
  • $\begingroup$ δ only specifies the transitions between states , considering your argument , δ doesn't have the power to change F , the only way to add or remove accept states is by changing F' , the set of accepting states directly , that being said it is true that we can change δ in a way that makes some accept state q unreachable , that doesn't change that q is an accept state, as for δ' all it says that when reading a string w if you try to make a transition FROM an accepting state q reject , 'reject' only occurs when we move from q , now can you guess what you missed ? $\endgroup$
    – Anazz
    Nov 12 '20 at 16:48
  • $\begingroup$ You claim that if we have 2 consecutive accepting states q and r in M' , then q cannot be accepting , well you are certainly correct but that will never happen ! What you missed is that δ' cuts all transitions from accepting states to any other state , even if q and r were consecutive in M , in M' the path from q to r is cut , so in M' no consecutive accepting states exist ! q remains accepting ,that doesn't contradict your statement , also r remains accepting since it may be reachable through another path in which no other accepting state comes before it, or it may become unreachable $\endgroup$
    – Anazz
    Nov 12 '20 at 16:52

A negation in the description of a given language, such as "none" and "not", is a strong indication that you should consider the complement of that language. Together with the property that regular language is closed under complementation, we can get a proof easily.

For problem a), consider its complement $$WITH\_PREFIX\_FROM(L)=\{u \in L\text{ at least one of the proper prefixes of }u\text{ belongs to }L\}.$$

Suppose $L$ is recognized by a DFA $D$. Let us build a new DFA $D'$ from $D$. $D'$ has exact the same states, alphabet, transition function and start state as $D$. For each state $s$ of $D$, if it can be reached by a word that contains a proper prefix that is in $L$, we will mark the corresponding state in $D'$ as a accept state of $D'$. Every state that reachable from those accept states will be marked as accept state as well. Now you can check that $WITH\_PREFIX\_FROM(L)$ is recognized by $D'$. As its complement, $NONPREFIX(L)$ is regular, too.

I will leave problem b) as an exercise.

  • $\begingroup$ "Every state that reachable from those accept states will be marked as accept state as well." That is not necessary, since every that kind of state has been marked as accept state. $\endgroup$
    – John L.
    Nov 11 '20 at 20:45
  • $\begingroup$ Wait a moment, apparently, I missed one fine detail of the problem. Updating ... $\endgroup$
    – John L.
    Nov 11 '20 at 20:47
  • $\begingroup$ It looks like I missed some more. Updating... $\endgroup$
    – John L.
    Nov 11 '20 at 22:05

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.