A Time-traveling NFA is an NFA that can jump around in time: thus, it can process its input in any order. For example, if an input x is equal to the string abcd, then a time-traveling NFA could instead process this input as if it were dbac. No position of the input can be repeated twice, however. A time-travling NFA checks all possible permutations of the input non-deterministically, and if any of these orderings leads to an accepting state after the input is fully processed, then the time-traveling NFA accepts. More formally, a Time-traveling NFA is described by a 5-tuple M = (Q, 2,90,8,F), where the ele- ments in the tuple are defined as in an NFA. We say that a time-traveling NFA accepts a string x if the following holds: For a permutation 1 : {1,..., n} {1,...,n}, let y = y1 - yn be such that Yr(i) = Xi, for all i {1,...,n}. We say that the time-traveling NFA accepts y if M accepts t(y) for some permutation a, where we treat M as an ordinary NFA. A language L is said to be a Time-traveling language if there exists a Time-traveling NFA M such that L = L(M). [15 points] (Part a) Show that the following language is Time-traveling. Provide a transition diagram of a Time-traveling NFA for this language. {w {0,1,2}* | (w has equal numbers of Os and 1s) OR (w has equal numbers of ls and 2s)}. [15 points] (Part a) Show that the following language is Time-traveling. Provide a transition diagram of a Time-traveling NFA for this language. {w {0,1,2}* | (w has equal numbers of Os and 1s) OR (w has equal numbers of ls and 2s)}. [5 points] (Part b) Give an example of a language that is regular but is not Time-traveling, and explain why your example is correct. [25 points] (Part c) Formally prove the following statement: If L is a Time-traveling language, then there is a number n 2 1 such that for any string x L of the form 0^1, where |x| 2 n, there exist a, with 1 Sa+B 0. [Note: The following lemma might be useful. You don't have to give a proof of the lemma.) Lemma 1. Any Time-traveling NFA can be transformed into a Time-traveling NFA which does not have any E transistions. [5 points] (Part d) Show that the following language is not Time-traveling: {w {0,1}* | a = b, where a = the number of Os in w, and b = the number of 1s in w}. Use Part (c) for it A Time-traveling NFA is an NFA that can jump around in time: thus, it can process its input in any order. For example, if an input x is equal to the string abcd, then a time-traveling NFA could instead process this input as if it were dbac. No position of the input can be repeated twice, however. A time-travling NFA checks all possible permutations of the input non-deterministically, and if any of these orderings leads to an accepting state after the input is fully processed, then the time-traveling NFA accepts. More formally, a Time-traveling NFA is described by a 5-tuple M = (Q, 2,90,8,F), where the ele- ments in the tuple are defined as in an NFA. We say that a time-traveling NFA accepts a string x if the following holds: For a permutation 1 : {1,..., n} {1,...,n}, let y = y1 - yn be such that Yr(i) = Xi, for all i {1,...,n}. We say that the time-traveling NFA accepts y if M accepts t(y) for some permutation a, where we treat M as an ordinary NFA. A language L is said to be a Time-traveling language if there exists a Time-traveling NFA M such that L = L(M). [15 points] (Part a) Show that the following language is Time-traveling. Provide a transition diagram of a Time-traveling NFA for this language. {w {0,1,2}* | (w has equal numbers of Os and 1s) OR (w has equal numbers of ls and 2s)}. [15 points] (Part a) Show that the following language is Time-traveling. Provide a transition diagram of a Time-traveling NFA for this language. {w {0,1,2}* | (w has equal numbers of Os and 1s) OR (w has equal numbers of ls and 2s)}. [5 points] (Part b) Give an example of a language that is regular but is not Time-traveling, and explain why your example is correct. [25 points] (Part c) Formally prove the following statement: If L is a Time-traveling language, then there is a number n 2 1 such that for any string x L of the form 0^1, where |x| 2 n, there exist a, with 1 Sa+B 0. [Note: The following lemma might be useful. You don't have to give a proof of the lemma.) Lemma 1. Any Time-traveling NFA can be transformed into a Time-traveling NFA which does not have any E transistions. [5 points] (Part d) Show that the following language is not Time-traveling: {w {0,1}* | a = b, where a = the number of Os in w, and b = the number of 1s in w}. Use Part (c) for it<><>