(All path to final state goes through it)īut if it goes through to final state through a original final state of X, the string could be split into two pieces where a prefix is in X and a suffix is in Y, that means the string has to be in X concatenate Y. Therefore we showed the non-deterministic Turing machine U precisely accept X union Y.Īssume language X and language Y are in NP, we wanted to show X concatenate Y is in NPīuild a new non-deterministic Turing machine C as follow:įor each final state in X, for each input symbol, write the same symbol back to the tape and jump to the start state of Y, and make it non-final.įor any string in X concatenate Y, it can follow the non-deterministic Turing machine X to go to final state of the original non-deterministic Turing machine X, jump to start state of Y, and then follow it to the final state of Y.įor any string, it cannot possibly go to a final state without going through a original final state of X. Take the union of state and transition function from both X and Y, that is a non-deterministic Turing machine U.įor any string in X, non-deterministic Turing machine U can take a non-deterministic jump to the start state of X, and follow the non-deterministic Turing machine X to finally get accepted.įor any string in Y, non-deterministic Turing machine U can take a non-deterministic jump to the start state of Y, and follow the non-deterministic Turing machine Y to finally get accepted.įor any string that is neither in X nor in Y, non-deterministic jump to either X or Y cannot lead to acceptance. Rename the states in Y so that it does not have the same name as in X.īuild a new non-deterministic Turing machine U as follow:Ĭreate a new start state, for each input symbol, it write the same symbol back to the tape, and non-deterministically go to the start state of X or the start state of Y. We can build non-deterministic Turing machine to solve the union language and the concatenation languageĪssume language X and language Y are in NP, we wanted to show X union Y is in NPīecause X and Y are in NP, there exists non-deterministic Turing machine X and non-deterministic Turing machine Y that verifies X and Y, respectively. Show that NP is closed under union and concatenation
0 Comments
Leave a Reply.AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |