patternMinor
O(n*log(n)) Turing Machine with exactly 1 tape for “equal number of a's and b's in a given word”?
Viewed 0 times
numberlogwithequalandtapewordformachineturing
Problem
I need to build a TM with exactly 1 tape for the language L = {w| w is a word with same number of a's and b's in it, for example: abba, aababb}
The TM has to have ONLY 1 tape and it has to run in O(nlog(n)) time. I understand how to do it in O(n^2) but i have no idea how to make it nlog(n).
If i have the input w = "aaaa....abbbbb....bb" for example, where w = a ^ n/2 * b ^n/2 (which is the worst case) then i will go backwards each time (to delete each a for each b) and the steps taken will be of size 1,2,3,4.....n. Sum(1 to n) is O(n^2)...
Help ? any ideas ?
The TM has to have ONLY 1 tape and it has to run in O(nlog(n)) time. I understand how to do it in O(n^2) but i have no idea how to make it nlog(n).
If i have the input w = "aaaa....abbbbb....bb" for example, where w = a ^ n/2 * b ^n/2 (which is the worst case) then i will go backwards each time (to delete each a for each b) and the steps taken will be of size 1,2,3,4.....n. Sum(1 to n) is O(n^2)...
Help ? any ideas ?
Solution
The idea is to repeatedly apply the following algorithm:
Each phase of the algorithm takes $O(n)$ steps, and there are $O(\log n)$ phases, for a total of $O(n\log n)$.
As an aside, using crossing sequences you can prove a matching lower bound of $\Omega(n\log n)$. Consider all inputs of the form $a^ib^{n-i} a^nb^n b^ja^{n-j}$. Such an input should be accepted iff $i = j$. For every input $x$, trace the execution of the Turing machine. When it crosses from the $n$th letter to the $(n+1)$th letter, record the state $\sigma$ of the Turing machine, and wait until the Turing machine crosses from the $2n$th letter to the $(2n+1)$th letter, at which time add $\sigma$ to the crossing sequence, and go back to waiting for it to cross from the $n$th letter to the $(n+1)$th letter. A cut-and-paste argument shows that the crossing sequence must depend on $i$, and so must be of length $\Omega(\log n)$ in the worst case, where the hidden constant depends on the number of states in the machine. Since it takes the machine $n$ steps to add a state to the crossing sequence, we obtain a lower bound of $\Omega(n \log n)$.
- Determine the parity of the number of $a$'s, deleting every second $a$ on the way.
- Determine the parity of the number of $b$'s, deleting every second $b$ on the way.
- Accept if there were no $a$'s or $b$'s.
- Reject if the parities are different.
- Jump back to Step 1.
Each phase of the algorithm takes $O(n)$ steps, and there are $O(\log n)$ phases, for a total of $O(n\log n)$.
As an aside, using crossing sequences you can prove a matching lower bound of $\Omega(n\log n)$. Consider all inputs of the form $a^ib^{n-i} a^nb^n b^ja^{n-j}$. Such an input should be accepted iff $i = j$. For every input $x$, trace the execution of the Turing machine. When it crosses from the $n$th letter to the $(n+1)$th letter, record the state $\sigma$ of the Turing machine, and wait until the Turing machine crosses from the $2n$th letter to the $(2n+1)$th letter, at which time add $\sigma$ to the crossing sequence, and go back to waiting for it to cross from the $n$th letter to the $(n+1)$th letter. A cut-and-paste argument shows that the crossing sequence must depend on $i$, and so must be of length $\Omega(\log n)$ in the worst case, where the hidden constant depends on the number of states in the machine. Since it takes the machine $n$ steps to add a state to the crossing sequence, we obtain a lower bound of $\Omega(n \log n)$.
Context
StackExchange Computer Science Q#91640, answer score: 5
Revisions (0)
No revisions yet.