Non-Deterministic Turing Machine-:
In a Non-Deterministic Turing Machine, for every state and symbol, there are a group of actions the TM can have. So, here the transitions are not deterministic. The computation of a non-deterministic Turing Machine is a tree of configurations that can be reached from the start configuration.
An input is accepted if there is at least one node of the tree which is an accept configuration, otherwise it is not accepted. If all branches of the computational tree halt on all inputs, the non-deterministic Turing Machine is called a Decider and if for some input, all branches are rejected, the input is also rejected.
A non-deterministic Turing machine can be formally defined as a 6-tuple (Q, X, ∑, δ, q0, B, F) where −
Q is a finite set of states
X is the tape alphabet
∑ is the input alphabet
δ is a transition function;
δ : Q × X → P(Q × X × {Left_shift, Right_shift}).
q0 is the initial state
B is the blank symbol
F is the set of final states
Conversion-:
Conversion from NDTM to DTM
In this section, we will discuss the method of converting NDTM to its equivalent DTM. In NDTM, when a specific input is given to the current state, the machine goes to multiple states. It can have zero, one or more than one move on a given input symbol. On the other hand, in DTM, when a specific input is given to the current state, the machine goes to only one state. DTM has only one move on a given input symbol.
Let, M = (Q, ∑, δ, q0, F) is an NDTM which accepts the language L(M). There should be equivalent DTM denoted by M' = (Q', ∑', q0', δ', F') such that L(M) = L(M').
Steps for converting NDTM to DTM:
Step 1: Initially Q' = ϕ
Step 2: Add q0 of NDTM to Q'. Then find the transitions from this start state.
Step 3: In Q', find the possible set of states for each input symbol. If this set of states is not in Q', then add it to Q'.
Step 4: In DTM, the final state will be all the states which contain F(final states of NDTM)
Example 1:
Convert the given NDTM to DTM.
Eg 1:- Pic 1
State |
0 |
1 |
→q0 |
q0 |
q1 |
q1 |
{q1, q2} |
q1 |
*q2 |
q2 |
{q1, q2} |
Solution: For the given transition diagram we will first construct the transition table.
Now we will obtain δ' transition for state q0.
1. δ'([q0], 0) = [q0]
2. δ'([q0], 1) = [q1]
The δ' transition for state q1 is obtained as:
1. δ'([q1], 0) = [q1, q2] (new state generated)
2. δ'([q1], 1) = [q1]
The δ' transition for state q2 is obtained as:
1. δ'([q2], 0) = [q2]
2. δ'([q2], 1) = [q1, q2]
Now we will obtain δ' transition on [q1, q2].
1. δ'([q1, q2], 0) = δ(q1, 0) ∪ δ(q2, 0)
2. = {q1, q2} ∪ {q2}
3. = [q1, q2]
4. δ'([q1, q2], 1) = δ(q1, 1) ∪ δ(q2, 1)
5. = {q1} ∪ {q1, q2}
6. = {q1, q2}
7. = [q1, q2]
The state [q1, q2] is the final state as well because it contains a final state q2. The transition table for the constructed DTM will be:
State |
0 |
1 |
→[q0] |
[q0] |
[q1] |
[q1] |
[q1, q2] |
[q1] |
*[q2] |
[q2] |
[q1, q2] |
*[q1, q2] |
[q1, q2] |
[q1, q2] |
The Transition diagram will be:
Eg- 1 Pic 2-
The state q2 can be eliminated because q2 is an unreachable state.
Example 2:
Convert the given NDTM to DTM.
Eg -2 Pic -: 1
Solution: For the given transition diagram we will first construct the transition table.
State |
0 |
1 |
→q0 |
{q0, q1} |
{q1} |
*q1 |
ϕ |
{q0, q1} |
Now we will obtain δ' transition for state q0.
1. δ'([q0], 0) = {q0, q1}
2. = [q0, q1] (new state generated)
3. δ'([q0], 1) = {q1} = [q1]
The δ' transition for state q1 is obtained as:
1. δ'([q1], 0) = ϕ
2. δ'([q1], 1) = [q0, q1]
Now we will obtain δ' transition on [q0, q1].
1. δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0)
2. = {q0, q1} ∪ ϕ
3. = {q0, q1}
4. = [q0, q1]
Similarly,
1. δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1)
2. = {q1} ∪ {q0, q1}
3. = {q0, q1}
4. = [q0, q1]
As in the given NDTM, q1 is a final state, then in DTM wherever, q1 exists that state becomes a final state. Hence in the DTM, final states are [q1] and [q0, q1]. Therefore set of final states F = {[q1], [q0, q1]}.
The transition table for the constructed DTM will be:
State |
0 |
1 |
→[q0] |
[q0, q1] |
[q1] |
*[q1] |
ϕ |
[q0, q1] |
*[q0, q1] |
[q0, q1] |
[q0, q1] |
The Transition diagram will be:
Eg 2-: Pic 2
Even we can change the name of the states of DTM.
Suppose
1. A = [q0]
2. B = [q1]
3. C = [q0, q1]
With these new names the DTM will be as follows:
Eq-: 2 Pic-3
Please write back for any inconvenience
Q6: Explain Nondeterministic Turing machines in detail. Also show how to convert non-deterministic Turing machine into...
please help deterministic turing machines. 3. Nondeterministic turing machines are a. less powerful than b. more powerful than c. just as powerful as d. not comparable with
Specify in detail a (deterministic) a Turing machine that accepts the language L = a* ba* (your Turing machine must halt on input w if, and only if, w € L). Remember: since your machine is deterministic, it must have a well-defined behavior for any possible symbol of the input alphabet, i.e, a, b, and #, in each state, except that you only need to ensure that your Turing machine behaves correctly when started in the configuration (s, #w#). Thus,...
Question 5 3 pts Which of the following is not equivalent to Turing Machines? Post Machine 2PDA Two-way Infinite Tape Turing Machine O Non-deterministic PDA
A Turing machine that halts on all inputs is called a halting Turing machine (also known as Decider). Prove the following: (a) If M1 and M2 are two halting Turing machines, then there exists a halting Turing machine that recognizes L(M1) ∩ L(M2). (b) If M1 and M2 are two (not necessarily halting) Turing machines, then there exists a Turing machine that recognizes L(M1) ∩ L(M2).
Draw a Turing Machine that increments a ternary number by 1. Also, explain your approach in brief. Note: For example, if the input is 22 (representing the decimal number 8), then the output should be 100 (representing the decimal number 9). For this task, consider a two-sided infinite tape Show the computation (sequence of configurations) of the above Turing Machine for input “22”.
1. Describe a Universal Turing Machine, and explain the significance of such a machine. 2. Explain the difference between countable and uncountable sets. 3. Explain the difference between recursive and recursively enumerable languages. 4. Describe the halting problem for Turing Machines and explain its significance to the field of Computer Science. 5. Is there a difference between the concepts of decidability and computability? If not, explain the concept. If so, explain the difference.
Turing Machines - Models of Language and Computation 8. (7 points) Consider the deterministic Turing machine M (s, t, h), includes fa, b, u) and possibly other symbols, H following rules, along with possibly other rules: (K, Σ, δ, s,H), where K (h), and includes the 6(s,凵) = (t,-) δ(t, a) = (t,-) 6(r,L) = (h, a) Here凵represents a blank. Suppose M is started in the configuration 凵aababaa in the start state with the read write head scanning the blank...
Subject : Theory of Computation Please answer , posting second time now cause nobody answered it previously Problem 3: Turing Machine Models Turing-Recognisablity and Decidability [20] a. Show that an FA with a FIFO queue is Turing universal (i.e equivalent in computational power to a Turing machine). You should regard this machine as being formally defined in a way that is very similar to a PDA, except that on each transition, instead of pushing and/or popping a character, the machine...
The UTM (universal Turing machine) operates with a fixed alphabet. We claim that the UTM can simulate any Turing machine, but the Turing machine (to be simulated) may have an input alphabet Σ (for example the Greek alphabet) and an output alphabet Ω (for example the English alphabet) which are different than the UTM’s alphabet. 1 Explain how a string over Σ can be converted to a string over the UTM’s alphabet, a process we can call CODING. 2 Explain...
Explain detail how you did it Thanks Convert 100 ft-lb to N-m