91Ó°ÊÓ

Construct a Turing machine with tape symbols 0, 1, and B that, given a bit string as input, replaces all but the leftmost 1 on the tape with 0s and does not change any of the other symbols on the tape.

Construct a Turing machine with tape symbols 0, 1, and B that, given a bit string as input, replaces the first two consecutive 1s on the tape with 0s and does not change any of the other symbols on the tape.

Construct a Turing machine that recognizes the set of all bit strings that end with a 0.

Construct a Turing machine that recognizes the set of all bit strings that end with a 0.

Construct a finite-state machine for entering a security code into an automatic teller machine (ATM) that implements these rules: A user enters a string of four digits, one digit at a time. If the user enters the correct four digits of the password, the ATM displays a welcome screen. When the user enters an incorrect string of four digits, the ATM displays a screen that informs the user that an incorrect password was entered. If a user enters the incorrect password three times, the account is locked.

Construct a finite-state machine that determines whether the word computer has been read as the last eight characters in the input read so far, where the input can be any string of English letters.

Construct a Turing machine that computes the function \(f(n)=n-3\) if \(n \geq 3\) and \(f(n)=0\) for \(n=0,1,2\) for all nonnegative integers \(n .\)

Construct a Turing machine that computes the function \(f(n)=n\) mod 3 for every nonnegative integer \(n .\)

A palindrome is a string that reads the same backward as it does forward, that is, a string \(w,\) where \(w=w^{R}\) , where \(w^{R}\) is the reversal of the string \(w\) . Find a context-free grammar that generates the set of all palindromes over the alphabet \(\\{0,1\\}\) .

Show that every nondeterministic finite-state automaton is equivalent to another such automaton that has the property that its starting state is never revisited.