Friday, March 5, 2010

NoPrefix and NoExtend

This is one interesting problem and I had some discussion about it with one of my classmates which gave a lot of insight to the problem. The problem can be found in Sipser 1.40.
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:

Unknown said...

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?

Math Formula?