Let $NOPREFIX(A)=\{w \in A| \textrm{ no proper prefix of }w \textrm{ is a member of }A\}$, and $NOEXTEND(A)=\{w \in A| w \textrm{ is not the proper prefix of any member of }A\}$. Show that the class of regular language is closed under these two operations.The DFA construction for both the cases is pretty interesting. In first case, i.e., for the case of $NOPREFIX(A)$, we have to remove all transitions from the set of final states of the DFA of $A$. That will ensure that after one acceptance, we cannot append some symbols to the string and accept it yet again.
For the construction of the second DFA, we have to be choosy about the new final states. We are going to make those old final states of $A$ as new final states of $NOEXTEND(A)$ from which there is no path to the set of final states.
The question is whether $NOPREFIX(A)=NOEXTEND(A)$ or not. My friend says that they are not equal. I agree to that, and I extend the fact to the conclusion that $NOPREFIX(A) \subseteq NOEXTEND(A)$, as I find the construction of the former is more stringent than the latter. I am not sure about this claim though. Hope you people can help me out.
1 comment:
I don't think that subset thing is correct.Take an example.Let A={10,101}.You can see that NoPrefix(a)={10} and NoExtend(A)={101}...So.....what do you think?
Post a Comment