91Ó°ÊÓ

Let \(T\) be the Turing machine defined by the five-tuples: \(\left(s_{0}, 0, s_{1}, 1, R\right), \quad\left(s_{0}, 1, s_{1}, 0, R\right), \quad\left(s_{0}, B, s_{1}, 0, R\right),\) \(\left(s_{1}, 0, s_{2}, 1, L\right),\left(s_{1}, 1, s_{1}, 0, R\right),\) and \(\left(s_{1}, B, s_{2}, 0, L\right) .\) For each of these initial tapes, determine the final tape when \(T\) halts, assuming that \(T\) begins in initial position.

Let \(T\) be the Turing machine defined by the five-tuples: \(\left(s_{0}, 0, s_{1}, 1, R\right), \quad\left(s_{0}, 1, s_{1}, 0, R\right), \quad\left(s_{0}, B, s_{1}, 0, R\right),\) \(\left(s_{1}, 0, s_{2}, 1, L\right),\left(s_{1}, 1, s_{1}, 0, R\right),\) and \(\left(s_{1}, B, s_{2}, 0, L\right) .\) For each of these initial tapes, determine the final tape when \(T\) halts, assuming that \(T\) begins in initial position.

Exercises \(1-3\) refer to the grammar with start symbol sentence, set of terminals \(T=\\{\text {the}, \text { sleepy, happy, tortoise, hare, }\) passes, runs, quickly, slowly \(\\}\) , set of nonterminals \(N=\\{\text { noun }\) phrase, transitive verb phrase, intransitive verb phrase, \(\mathrm{~ a r t i c l e , ~ a d j e c t i v e , ~ n o u n , ~ v e r b , ~ a d v e r b \\} , ~ a n d ~ p r o d u c t i o n s : ~}\) $$ \begin{array}{l}{\text { sentence } \rightarrow \text { noun phrase transitive verb phrase }} \\ {\text { noun phrase }} \\ {\text { sentence } \rightarrow \text { noun phrase intransitive verb phrase }} \\ {\text { noun phrase } \rightarrow \text { article adjective noun }} \\ {\text { noun phrase } \rightarrow \text { article noun }}\end{array} $$ $$ \begin{array}{l}{\text { transitive verb phrase } \rightarrow \text { transitive verb }} \\ {\text { intransitive verb phrase } \rightarrow \text { intransitive verb adverb }} \\ {\text { intransitive verb phrase } \rightarrow \text { intransitive verb }} \\ {\text { article } \rightarrow \text { the }}\end{array} $$ $$ \begin{array}{l}{\text { adjective } \rightarrow \text { sleepy }} \\ {\text { adjective } \rightarrow \text { happy }} \\ {\text { noun } \rightarrow \text { tortoise }} \\ {\text { noun } \rightarrow \text { hare }} \\ {\text { transitive verb } \rightarrow \text { passes }} \\ {\text { intransitive verb } \rightarrow \text { runs }} \\ {\text { adverb } \rightarrow \text { quickly }} \\ {\text { adverb } \rightarrow \text { slowly }}\end{array} $$ Find five other valid sentences, besides those given in Exercise \(1 .\)

Express each of these sets using a regular expression. a) the set consisting of the strings \(0,11,\) and 010 b) the set of strings of three 0 s followed by two or more 0 \(\mathrm{s}\) c) the set of strings of odd length d) the set of strings that contain exactly one 1 e) the set of strings ending in 1 and not containing 000

What does the Turing machine described by the five-tuples \(\left(s_{0}, 0, s_{0}, 1, R\right),\left(s_{0}, 1, s_{0}, 1, R\right),\left(s_{0}, B, s_{1}, B, L\right),\) \(\left(s_{1}, 1, s_{2}, 1, R\right),\) do when given a) 11 as input? b) a bit string consisting entirely of 1s as input?

Let \(V\) be an alphabet, and let \(A\) and \(B\) be subsets of \(V^{*}\) . Show that \(|A B| \leq|A||B| .\)

Construct a Turing machine with tape symbols 0, 1, and B that, when given a bit string as input, adds a 1 to the end of the bit string and does not change any of the other symbols on the tape.

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

Construct a finite-state machine that models a newspaper vending machine that has a door that can be opened only after either three dimes (and any number of other coins) or a quarter and a nickel (and any number of other coins) have been inserted. Once the door can be opened, the customer opens it and takes a paper, closing the door. No change is ever returned no matter how much extra money has been inserted. The next customer starts with no credit.

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