patternMinor
Mapping many transition functions into two transition functions
Viewed 0 times
functionsintotwotransitionmanymapping
Problem
Continuing from this answer: https://cs.stackexchange.com/a/56072/43035
I don't understand how it's possible to map many transition functions $\delta_1,...,\delta_n$ of a NDTM into just two transition functions $\delta_0',\delta_1'$. How will conflicts be handled?
For example: $\delta_1(q_1, a) = (q_2, b, R)\\ \delta_2(q_1, a) = (q_3, c, L)\\ \delta_3(q_1, a) = (q_4, d, R)$
How can you map $\delta_3$?
I don't understand how it's possible to map many transition functions $\delta_1,...,\delta_n$ of a NDTM into just two transition functions $\delta_0',\delta_1'$. How will conflicts be handled?
For example: $\delta_1(q_1, a) = (q_2, b, R)\\ \delta_2(q_1, a) = (q_3, c, L)\\ \delta_3(q_1, a) = (q_4, d, R)$
How can you map $\delta_3$?
Solution
Suppose that you have three options $o_1,o_2,o_3$.
You first guess whether to apply $o_1$ or not; if not, you stay in place.
If you didn't apply $o_1$, you guess whether to apply $o_2$ or $o_3$.
Here is how to implement it using transitions, using your example:
$$
\begin{align*}
&\delta_1(q_1,a) = (q_2,b,R) \\
&\delta_2(q_1,a) = (q_s,a,R) \\
&\delta_1(q_s,\sigma) = (q_t,\sigma,L) \\
&\delta_2(q_s,\sigma) = (q_t,\sigma,L) \\
&\delta_1(q_t,a) = (q_3,c,L) \\
&\delta_2(q_t,a) = (q_4,d,R)
\end{align*}
$$
Here $q_s,q_t$ are new states, and $\sigma$ is any tape symbol.
You first guess whether to apply $o_1$ or not; if not, you stay in place.
If you didn't apply $o_1$, you guess whether to apply $o_2$ or $o_3$.
Here is how to implement it using transitions, using your example:
$$
\begin{align*}
&\delta_1(q_1,a) = (q_2,b,R) \\
&\delta_2(q_1,a) = (q_s,a,R) \\
&\delta_1(q_s,\sigma) = (q_t,\sigma,L) \\
&\delta_2(q_s,\sigma) = (q_t,\sigma,L) \\
&\delta_1(q_t,a) = (q_3,c,L) \\
&\delta_2(q_t,a) = (q_4,d,R)
\end{align*}
$$
Here $q_s,q_t$ are new states, and $\sigma$ is any tape symbol.
Context
StackExchange Computer Science Q#76171, answer score: 4
Revisions (0)
No revisions yet.