It is possible to offer another algorithm to decide the language A of example 3.7:
In any step we delete the right half of the 0-s that are still written on the tape. We continue with this process until we reach a point at which the number of 0-s is odd and greater than 1 - Which is rejected, or until we reach a single zero - which is accepted.
Present a full description of a Turing Machine that implements the algorithm (as in figure 3.8 in the book).
The tape alphabet is: Γ = {0,x , ⌴ }
The machine won’t have more than 10 states (including q_{accept} and q_{reject })
Explain well the machine operation and why it indeed decides the language A.
Build a Turing Machine that when it receives as input the word ‘w’ above the alphabet {0,1}, it is ending in a state q_{accept} and on the tape the word ‘w’ is written and afterwards
0-s as the number of 0-s in ‘w’.
For example, if: w=0110010, then at the end of the run, on the tape the word 01100100000 will be written.
Input alphabet is Σ={0,1}, Tape alphabet is Γ = {0,1 , ⌴ } The machine won’t have more than 10 states (including q_{accept })
Comment: The machine won’t have a q_{reject} state.
Describe the machine with a figure.
Explain well the machine operation and why it indeed follows the requirements. Remember to handle correctly the case in which ‘w’ is the empty word.
Pay attention that the tape alphabet is Γ = {0,1 , ⌴ }
We will observe the following computation module: Turing Machine with infinite states . This machine is identical to a regular machine. Accept that the number of states could be infinite.
Does this machine have more computational power than a regular machine?
If you answered ‘yes’, show that a machine with infinite states can recognize languages that can’t be recognized with a machine that has a finite number of states. In addition, explain why the existence of such a machine doesn’t contradict the Church-Turing Thesis.
If you answered ‘no’, show how a machine with a finite number of states could imitate the operation of a machine with an infinite number of states.
A natural number is called composite if it is not a prime number (which means, equals 1, or has other dividers except 1 and itself).
F = {a^{n }| n≥1; n is composite }
The detail level of the description should be similar to the machine M_{3} from example 3.11 in the book.
The machine should use nondeterminism in a way that would ease the computations (In comparison to a deterministic machine for the same task). Pay attention: The machine you describe decides the language (and not just recognizes it).
Explain well your answer.
Build an enumerator to language A of example 3.7.
The alphabet Σ of the output tape will be {0}, the alphabet Γ of the work-tape will be
Γ = {0,x , ⌴ }
The enumerate won’t have more than 8 states( including qhalt and qprint )
Describe in enumerator using a figure (as the figure 3.10 in the book, no need to include q_{halt }and all the edges that enter it. No need to draw impossible transitions).
Explain well how the enumerator works and why it indeed enumerates the language A.
Language L is a non trivial language above alphabet Σ (L≠⊘ and L≠ Σ^{* })
An Alternate Enumerator for language L is an enumerator that prints an infinite series of words: w1, w2, … in which:
In other words, the enumerator prints one time a word which belongs to L and afterwards a word which doesn’t belong to L.
Every word in Σ^{* }eventually is printed, since any such word either belongs to L or not.
It is possible to have words printed more than one time.
Our motto is deliver assignment on Time. Our Expert writers deliver quality assignments to the students.
Get reliable and unique assignments by using our 100% plagiarism-free services.
The experienced team of AssignmentHippo has got your back 24*7. Get connected with our Live Chat support executives to receive instant solutions for your assignment problems.
We can build quality assignments in the subjects you're passionate about. Be it Programming, Engineering, Accounting, Finance and Literature or Law and Marketing we have an expert writer for all.
Get premium service at a pocket-friendly rate. At AssignmentHippo, we understand the tight budget of students and thus offer our services at highly affordable prices.