SWAP(L):={swap(w)|winL}, where
swap(w) is defined recursively as\
swap(w):={(w if |w|\ Our goal is to show that if
L is regular, then
SWAP(L) will also be regular. Since
L is regular, we can\ assume that there exists a DFA
M which accepts
L. In order to show that SWAP
(L) is regular, we will use\
M to construct a DFA
M^(') which accepts SWAP
(L).\ In these types of problems, the most important part of the problem-solving process is to write down English\ descriptions of what the states in
M^(') mean. Once we have descriptions of the states' meanings, it is much\ easier to reason about what the transitions, start state, and accept states should be.\ In this GPS, we will provide some scaffolding by giving you these English descriptions. However, don't forget\ to do this step on your own on homework and exams!\ Intuitively,
M^(') will read the string in two character chunks, swap the two characters, and simulate
M\ on the swapped pair of characters. This means that when
M^(') reads an odd-indexed character; it\ cannot immediately simulate
M on that character. Instead, it must remember that odd-indexed\ character until it reads the next (even-indexed) character, so that it can swap those two characters and\ feed them to the simulation of
M. Keeping this intuition in mind, we will now make the description more\ formal.\ Every state
q in the DFA
M will correspond to
|\\\\Sigma |+1 states in
M^('), as described below:\ The state
(q,\\\\epsi ) means that the simulation of
M is in state
q, and the number of characters read\ so far is even.\ For each character
ain\\\\Sigma , the state
(q,a) means that the simulation of
M is in state
q, the\ number of characters read so far is odd, and the last character read was
a. (In this state, the last\ character
a has not yet been fed to the simulation of
M )\ Note that our transformation cannot assume anything about
M;M can be any arbitrary DFA. However, in\ order to scaffold the learning process, we will first focus on a concrete example and consider what our\ transformation does to a specific DFA
M. In the following problems, we will generalize the transformation to\ an abstract
M.\ Consider the DFA
M shown above. If we construct
M^(')=(Q^('),{0,1},\\\\delta ^('),s^('),A^(')) from
M in accordance\ with the specification of states above, then what are the components of
M^(') ?\ (Note that we're only asking for a few representative examples of the transition function instead of asking\ you to fill out the entire transition table for
\\\\delta ^(').)\ To represent a set, input a comma-separated list surrounded by curly braces. For example, write
{a,b,c} for\ a set containing states
a,b, and
c. Note that some input fields below might not require braces. If your\ answer is the empty set, please write an empty set "
swap(w):={wbaswap(x)ifw1ifw=abxforsomea,bandx Our goal is to show that if L is regular, then SWAP(L) will also be regular. Since L is regular, we can assume that there exists a DFA M which accepts L. In order to show that SWAP(L) is regular, we will use M to construct a DFA M which accepts SWAP(L). In these types of problems, the most important part of the problem-solving process is to write down English descriptions of what the states in M mean. Once we have descriptions of the states' meanings, it is much easier to reason about what the transitions, start state, and accept states should be. In this GPS, we will provide some scaffolding by giving you these English descriptions. However, don't forget to do this step on your own on homework and exams! Intuitively, M will read the string in two character chunks, swap the two characters, and simulate M on the swapped pair of characters. This means that when M reads an odd-indexed character; it cannot immediately simulate M on that character. Instead, it must remember that odd-indexed character until it reads the next (even-indexed) character, so that it can swap those two characters and feed them to the simulation of M. Keeping this intuition in mind, we will now make the description more formal. Every state q in the DFA M will correspond to +1 states in M, as described below: - The state (q,) means that the simulation of M is in state q, and the number of characters read so far is even. - For each character a, the state (q,a) means that the simulation of M is in state q, the number of characters read so far is odd, and the last character read was a. (In this state, the last character a has not yet been fed to the simulation of M ) Note that our transformation cannot assume anything about M;M can be any arbitrary DFA. However, in order to scaffold the learning process, we will first focus on a concrete example and consider what our transformation does to a specific DFA M. In the following problems, we will generalize the transformation to an abstract M. Consider the DFA M shown above. If we construct M=(Q,{0,1},,s,A) from M in accordance with the specification of states above, then what are the components of M ? (Note that we're only asking for a few representative examples of the transition function instead of asking you to fill out the entire transition table for .) To represent a set, input a comma-separated list surrounded by curly braces. For example, write {a,b,c} for a set containing states a,b, and c. Note that some input fields below might not require braces. If your answer is the empty set, please write an empty set " } " or copy and paste " ". Order of elements does not matter. Copy and paste the symbol to represent . Q= ((1,),1)= ((1,),0)= ((2,1),1)= ((1,1),0)= ((0,0),1)= ((2,0),0)= s= A= swap(w):={wbaswap(x)ifw1ifw=abxforsomea,bandx Our goal is to show that if L is regular, then SWAP(L) will also be regular. Since L is regular, we can assume that there exists a DFA M which accepts L. In order to show that SWAP(L) is regular, we will use M to construct a DFA M which accepts SWAP(L). In these types of problems, the most important part of the problem-solving process is to write down English descriptions of what the states in M mean. Once we have descriptions of the states' meanings, it is much easier to reason about what the transitions, start state, and accept states should be. In this GPS, we will provide some scaffolding by giving you these English descriptions. However, don't forget to do this step on your own on homework and exams! Intuitively, M will read the string in two character chunks, swap the two characters, and simulate M on the swapped pair of characters. This means that when M reads an odd-indexed character; it cannot immediately simulate M on that character. Instead, it must remember that odd-indexed character until it reads the next (even-indexed) character, so that it can swap those two characters and feed them to the simulation of M. Keeping this intuition in mind, we will now make the description more formal. Every state q in the DFA M will correspond to +1 states in M, as described below: - The state (q,) means that the simulation of M is in state q, and the number of characters read so far is even. - For each character a, the state (q,a) means that the simulation of M is in state q, the number of characters read so far is odd, and the last character read was a. (In this state, the last character a has not yet been fed to the simulation of M ) Note that our transformation cannot assume anything about M;M can be any arbitrary DFA. However, in order to scaffold the learning process, we will first focus on a concrete example and consider what our transformation does to a specific DFA M. In the following problems, we will generalize the transformation to an abstract M. Consider the DFA M shown above. If we construct M=(Q,{0,1},,s,A) from M in accordance with the specification of states above, then what are the components of M ? (Note that we're only asking for a few representative examples of the transition function instead of asking you to fill out the entire transition table for .) To represent a set, input a comma-separated list surrounded by curly braces. For example, write {a,b,c} for a set containing states a,b, and c. Note that some input fields below might not require braces. If your answer is the empty set, please write an empty set " } " or copy and paste " ". Order of elements does not matter. Copy and paste the symbol to represent . Q= ((1,),1)= ((1,),0)= ((2,1),1)= ((1,1),0)= ((0,0),1)= ((2,0),0)= s= A=
