Logout Open In App
Open In App
Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Chapter 13: Q25E (page 898)

Construct a Turing machine that computes the function \(f\left( {{n_1},{n_2}} \right) = {\rm{min}}\left( {{n_1},{n_2}} \right)\) for all nonnegative integers \({n_1}\) and \({n_2}\).

Short Answer

Expert verified

The constructed Turing machine that computes the function\(f\left( {{n_1},{n_2}} \right) = {\rm{min}}\left( {{n_1},{n_2}} \right)\)for all nonnegative integers\({n_1}\)and\({n_2}\)is

\(\begin{array}{c}\left( {{s_0},0,{s_0},0,R} \right),\left( {{s_0}^*,{s_5},B,R} \right),\left( {{s_5},1,{s_5},B,R} \right),\left( {{s_5},0,{s_5},B,R} \right),\\\left( {{s_5},B,{s_6},B,L} \right),\left( {{s_5},B,{s_5},B,L} \right),\left( {{s_5},0,{s_7},1,L} \right),\left( {{s_7},0,{s_7},1,L} \right),\\\left( {{s_0},1,{s_1},0,R} \right),\left( {{s_1},1,{s_1},1,R} \right),\left( {{s_1}{,^*},{s_2}{,^*},R} \right),\left( {{s_2},0,{s_2},0,R} \right),\\\left( {{s_2},l,{s_3},O,L} \right),\left( {{s_2},B,{s_4},B,L} \right),\left( {{s_3}{,^*},{s_3},L} \right),\left( {{s_3},0,{s_3},0,L} \right),\\\left( {{s_3},1,{s_3},1,L} \right),\left( {{s_3},B,{s_0},B,R} \right),\left( {{s_4},0,{s_4},1,L} \right),\left( {{s_4},0,{S_5},B,L} \right),\\\left( {{s_5},0,{s_5},B,L} \right),\left( {{s_5},1,{s_5},B,L} \right)\end{array}\)

Step by step solution

Achieve better grades quicker with Premium

  • Unlimited AI interaction
  • Study offline
  • Say goodbye to ads
  • Export flashcards
Start your free trial Skip

Over 22 million students worldwide already upgrade their learning with Vaia!

01

Definition

A Turing machine \(T = \left( {S,I,f,{s_0}} \right)\) consists of a finite set \(S\) of states, an alphabet \({\bf{I}}\) containing the blank symbol \(B\), a partial function \(f\) from \(S \times I\) to \(S \times I \times \left\{ {R,L} \right\}\), and a starting state \({s_0}\).

The idea here is to match off the \(1\)'s in the two inputs (changing the \(1\)'s to 0’s from the left, say, to keep track), until one of them is exhausted. At that point, you need to erase the larger input entirely (as well as the asterisk) and change the \({\bf{0}}'s\) back to \(1's\). Here is how you'll do it. In state \({{\bf{s}}_{\bf{0}}}\)you skip over any \({\bf{0}}'s\) until you come to either a 1 or the \(*\)If it's the, then you know that the second input \({n_2}\) is at least as large as the first \({n_1}\), so you enter a clean-up state \({s_5}\), which erases the asterisk and all the \(0's\) and \(1's\) to its right.

02

Defining five-tuples

The five-tuples for this much are \(\left( {{s_0},0,{s_0},0,R} \right),\left( {{s_0},{s_5},\;B,R} \right),\left( {{s_5},1,{s_5},\;B,R} \right)\), and \(\left( {{s_5},0,{s_5},\;B,R} \right)\). Once this erasing is finished, you need to go over to the part of the tape where the first input was and change all the \({\bf{0}}'s\) back to \(1's\); the following transitions accomplish this: \(\left( {{s_5},\;B,{s_6},\;B,\;L} \right),\left( {{s_5},\;B,{s_5},\;B,\;L} \right),\left( {{s_5},0,{s_7},1,L} \right)\), and \(\left( {{s_7},0,{s_7},1,L} \right)\). Eventually, the machine halts in state \({s_7}\) when the blank preceding the original input is encountered.

03

Construction of Turing machine

The other possibility is that the machine encounters a \(1\) while in state so. Want to change this \(1\) to a 0, skip over any remaining \(1's\) as well as the asterisk, skip over any \({\bf{0}}'s\) to the right of the asterisk (these represent parts of \({n_2}\) that have already been matched off against equal parts of \({n_1}\), and then either find \(1\) in \({n_2}\) (which change to a \({\bf{0}}\)) or else come to the blank at the end of the input. Here are the transitions: \(\left( {{s_0},1,{s_1},0,R} \right),\left( {{s_1},1,{s_1},1,R} \right),\left( {{s_1}{,^*},{s_2}{,^*},R} \right),\left( {{s_2},0,{s_2},0,R} \right),\left( {{s_2},1,{s_3},0,\;L} \right),\left( {{s_2},\;B,{s_4},\;B,\;L} \right)\)

04

Construction of Turing machine

At this point you are either in state \({s_3}\), ready to go back for the next iteration, or in state \({s_4}\) ready for some cleanup. In the former case, you want to skip back over the nonblank symbols until you reach the start of the string, so you add five-tuples \(\left( {{s_3}{,^*},{s_3},L} \right),\left( {{s_3},0,{s_3},0,L} \right),\left( {{s_3},1,{s_3},1,L} \right)\), and \(\left( {{s_3},B,{s_0},B,R} \right)\). In the latter case, you know that the first string is longer than the second. Therefore, you want to change the \({\bf{0}}'s\) in the second input string back to \(1's\) and then erase the asterisk and remnants of the first input string. Here are the transitions:

\(\left( {{s_4},0,{s_4},1,\;L} \right),\left( {{s_4},0,{S_5},B,L} \right),\left( {{s_5},0,{s_5},\;B,\;L} \right),\left( {{s_5},1,{s_5},\;B,\;L} \right)\).

Hence, the constructed Turing machine that computes the function\(f\left( {{n_1},{n_2}} \right) = {\rm{min}}\left( {{n_1},{n_2}} \right)\)for all nonnegative integers\({n_1}\)and\({n_2}\)is

\(\begin{array}{c}\left( {{s_0},0,{s_0},0,R} \right),\left( {{s_0}^*,{s_5},B,R} \right),\left( {{s_5},1,{s_5},B,R} \right),\left( {{s_5},0,{s_5},B,R} \right),\\\left( {{s_5},B,{s_6},B,L} \right),\left( {{s_5},B,{s_5},B,L} \right),\left( {{s_5},0,{s_7},1,L} \right),\left( {{s_7},0,{s_7},1,L} \right),\\\left( {{s_0},1,{s_1},0,R} \right),\left( {{s_1},1,{s_1},1,R} \right),\left( {{s_1}{,^*},{s_2}{,^*},R} \right),\left( {{s_2},0,{s_2},0,R} \right),\\\left( {{s_2},l,{s_3},O,L} \right),\left( {{s_2},B,{s_4},B,L} \right),\left( {{s_3}{,^*},{s_3},L} \right),\left( {{s_3},0,{s_3},0,L} \right),\\\left( {{s_3},1,{s_3},1,L} \right),\left( {{s_3},B,{s_0},B,R} \right),\left( {{s_4},0,{s_4},1,L} \right),\left( {{s_4},0,{S_5},B,L} \right),\\\left( {{s_5},0,{s_5},B,L} \right),\left( {{s_5},1,{s_5},B,L} \right)\end{array}\)

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Give production rules in extended Backus–Naur form that generate all decimal numerals consisting of an optional sign, a nonnegative integer, and a decimal fraction that is either the empty string or a decimal point followed by an optional positive integer optionally preceded by some number of zeros.

let \({{\bf{G}}_{\bf{1}}}\) and \({{\bf{G}}_{\bf{2}}}\) be context-free grammars, generating the language\({\bf{L}}\left( {{{\bf{G}}_{\bf{1}}}} \right)\) and \({\bf{L}}\left( {{{\bf{G}}_{\bf{2}}}} \right)\), respectively. Show that there is a context-free grammar generating each of these sets.

a) \({\bf{L}}\left( {{{\bf{G}}_{\bf{1}}}} \right){\bf{UL}}\left( {{{\bf{G}}_{\bf{2}}}} \right)\)

b) \({\bf{L}}\left( {{{\bf{G}}_{\bf{1}}}} \right){\bf{L}}\left( {{{\bf{G}}_{\bf{2}}}} \right)\)

c) \({\bf{L}}{\left( {{{\bf{G}}_{\bf{1}}}} \right)^{\bf{*}}}\)

Let V = {S, A, B, a, b} and T = {a, b}. Find the language generated by the grammar (V, T, S, P) when theset P of productions consists of

\(\begin{array}{*{20}{l}}{{\bf{a) S }} \to {\bf{ AB, A }} \to {\bf{ ab, B }} \to {\bf{ bb}}{\bf{.}}}\\{{\bf{b) S }} \to {\bf{ AB, S }} \to {\bf{ aA, A }} \to {\bf{ a, B }} \to {\bf{ ba}}{\bf{.}}}\\{{\bf{c) S }} \to {\bf{ AB, S }} \to {\bf{ AA, A }} \to {\bf{ aB, A }} \to {\bf{ ab, B }} \to {\bf{ b}}{\bf{.}}}\\{{\bf{d) S }} \to {\bf{ AA, S }} \to {\bf{ B, A }} \to {\bf{ aaA, A }} \to {\bf{ aa, B }} \to {\bf{ bB, B }} \to {\bf{ b}}{\bf{.}}}\\{{\bf{e) S }} \to {\bf{ AB, A }} \to {\bf{ aAb, B }} \to {\bf{ bBa, A }} \to {\bf{ \lambda , B }} \to {\bf{ \lambda }}{\bf{.}}}\end{array}\)

Let \({\bf{G = }}\left( {{\bf{V, T, S, P}}} \right)\) be the context-free grammar with \({\bf{V = }}\left\{ {\left( {\bf{,}} \right){\bf{S,A,B}}} \right\}{\bf{, T = }}\left\{ {\left( {\bf{,}} \right)} \right\}\) starting symbol \({\bf{S}}\), and productions

Show that \({\bf{L}}\left( {\bf{G}} \right)\) is the set of all balanced strings of parentheses, defined in the preamble to Supplementary Exercise \(55\) in Chapter \(4\).

Let V be an alphabet, and let A and B be subsets of \({\bf{V*}}\) with A⊆B. Show that \({\bf{A*}}\)⊆B*.
See all solutions

Recommended explanations on Math Textbooks

Applied Mathematics

Read Explanation

Probability and Statistics

Read Explanation

Pure Maths

Read Explanation

Theoretical and Mathematical Physics

Read Explanation

Discrete Mathematics

Read Explanation

Decision Maths

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free