Write a 2 tape Turing machine that converts its input from binary to unary. In other words, if the input is the string x ∈ {$, 0, 1}∗, a $ followed by the binary expansion of the nonnegative integer n (for example, $101 to represent n = 5), then the machine outputs the string 1^n(e.g., 1^5 = 11111). You may assume the input string will be in this format, i.e., a $ followed by either just a 0, or followed by a binary string beginning with 1.

Write a 2 tape Turing machine that converts its input from binary to unary. In other words, if the input is the string x ∈ {$, 0, 1}∗, a $ followed by the binary expansion of the nonnegative integer n (for example, $101 to represent n = 5), then the machine outputs the string 1^n(e.g., 1^5 = 11111). You may assume the input string will be in this format, i.e., a $ followed by either just a 0, or followed by a binary string beginning with 1.

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter8: Arrays And Strings

Section: Chapter Questions

Problem 24PE

See similar textbooks

Similar questions

Please write Turing machine code that computes the function f(x) = 3x. Below is an example of some Turing machine code for reference on how the code should look. this does NOT mean that this is the correct way to start the code. this is just an example of the format I need. 1,B,R,2 2,1,R,2 2,B,1,3 3,1,L,3 Assuming x = 2, the starting tape should look like this: B|1|1|B and end up like thisB|1|1|1|1|1|1|B Or if x = 3, the starting tape should look like this:B|1|1|B and end up like thisB|1|1|1|1|1|1|1|1|1|B Please do not use chatgpt for this, it does not compute the correct answer I tried a million times. I keep getting answers from tutors here that are from chatgpt and it always ends up being incorrect for Turing machine code. Please feel free to check your answer with this Turing machine editor: https://amrits7.github.io/TuringMachineEditor/
TM binary to unary conversion: Write a Turing machine that converts its input from binary to unary. In other words, if the input is the string x € {$,0,1}*, a $ followed by the binary expansion of the nonnegative integer n (for example, $101 to represent n = 5), then the machine outputs the string 1" (e.g., 15 = 11111). You may assume the input string will be in this format, i.e., a $ followed by either just a 0, or followed by a binary string beginning with 1. Format the Turing machine
Write a program to determine the possible location(s) of a missing symbol of enclosure given a mathematical representation of a string. Although spaces are used between characters for readability, the input string will have no spaces. All operands will be integers less than 1000, and the order of evaluation for the symbols is parentheses, brackets and then braces. For example: {[(2 + 3) * 6 / 10} - One bracket is missing. It could be correctly placed in several locations: {[(2 + 3)] * 6 / 10} -Location 8 {[(2 + 3) * 6] / 10} -Location 10 {[(2 + 3) * 6 / 10]} -Location 13 Input from the keyboard a string of characters with no spaces representing a mathematical expression. The first position of the string will start at number 1. Each type of symbol of enclosure will be used at most once, and each expression will have at least one missing symbol of enclosure. The operators used will be: +, −, * and /. Single integers will never be enclosed. For each line of input list output to the screen…
I need to write a Java program to count the number of muck-free regions in a lagoon. The Lagoon is represented by a rectangle of N x M squares. Each square contains either muck ('M') or sand ('.'). A region is defined as a connected set of one of more squares with sand in it, where a square is considered to connect to all eight of its adjacent squares. Sample input/output is shown in picture attached
Consider the language L = {a'b'ck | i+k = j}. In a proof that L is not regular, you would assume Lis regular, with pumping length p and then choose a string that causes problems when pumped. Some of the following are designed to make the task easy. Place a check next to each that allows a relatively easy argument. aaabbbbc aPbP bPcP aPbPcP ap/26PCP/2 aPb2PcP
Lets say we are creating a python game. A word is displayed gets displayed on the screen. The players of the game must type as many words as they an that are related to the word that is displayed. If players type in the same word multiple times, it is ignored. One the players are done taking turns, the program gives each player a score that is based off how many wrods they entered that are similiar to what other words players have entered. So for a player to get a point, the word they typed must be typed by another student. QUESTION: We need to store the words typed by the players and all words etered. Would we use a list, set, dict or tuple?
Write a program that reads two matrices of integers. It then generates the sum, difference and productof the two matrices.The sum of the two matrices of the same size is a matrix with elements that are the sums of thecorresponding elements of the two given matrices. Addition is not defined for matrices of different sizes.If A and B are matrices of the same size, then we define subtraction as follows: A – B = A + (-B). Thus, tosubtract matrix B from matrix A, we simply subtract corresponding elements.To multiply a matrix by another matrix we need to do the "dot product" of rows and columns. The "DotProduct" is where we multiply matching members, then sum up:(1, 2, 3) • (7, 9, 11) = 1×7 + 2×9 + 3×11 = 58We match the 1st members (1 and 7), multiply them, likewise for the 2nd members (2 and 9) and the3rd members (3 and 11), and finally sum them up.
Write a program that reads two matrices of integers. It then generates the sum, difference and productof the two matrices.The sum of the two matrices of the same size is a matrix with elements that are the sums of thecorresponding elements of the two given matrices. Addition is not defined for matrices of different sizes.If A and B are matrices of the same size, then we define subtraction as follows: A – B = A + (-B). Thus, tosubtract matrix B from matrix A, we simply subtract corresponding elements.To multiply a matrix by another matrix we need to do the "dot product" of rows and columns. The "DotProduct" is where we multiply matching members, then sum up:(1, 2, 3) • (7, 9, 11) = 1×7 + 2×9 + 3×11 = 58We match the 1st members (1 and 7), multiply them, likewise for the 2nd members (2 and 9) and the3rd members (3 and 11), and finally sum them up.Use the following definitions:#define ROW 6#define COL 6void add (int matrixResult[] [COL], int matrixA[] [COL], int matrixB[][COL],int row, int…
We have n glasses which can hold a varying amount of liquid. We will say that glass1 is size q1 quarts and glass2 is size q2 quarts, etc. We now give you a size, say x quarts. You must give me a glass of exactly x quarts. You are allowed to fill any glass to exactly its size and to pour any liquid from one glass into another. When you pour, you either have to empty the glass you are pouring from or fill the glass you are pouring into. Can you do it?More concrete example: G1 has size 10 quarts. G2 has size 4 quarts. G3 has size 1 quart. You can get a 5 quart drink by filling G1, pouring 4 quarts from it into G2 and 1 quart of it into G1. After that, G1 has exactly 5 quarts. In the same problem, we could get 8 quarts by filling G2 twice and emptying it into G1 twice. Given This: Write an algorithm to do this and determine its complexity.
Given a word of length n and n five-sided dice with a character on each side. Find out if this word can be constructed by the set of given dice. Example 1 Input: word = "hello" dice = [[a, l, c, d, e], [a, b, c, d, e], [a, b, c, h, e], [a, b, c, d, o], [a, b, c, l, e]] Output: true Explanation: dice[2] + dice[1] + dice[0] + dice[4] + dice[3] Example 2 Input: word = "hello" dice = [[a, b, c, d, e], [a, b, c, d, e], [a, b, c, d, e], [a, b, c, d, e], [a, b, c, d, e]] Output: false Example 3 Input: word = "aaaa" dice = [[a, a, a, a, a], [b, b, b, b, b], [a, b, c, d, e], [a, b, c, d, e]] Output: false (a) Frame this problem as a network flow problem; Give a graph showing the nodes with sources and sinks and give a rationale for your formulation. (b) To implement this, what algorithm(s) would you use? What is the running time of the algorithm? Why does it work (You can use exchange arguments to provide a proof)
The operation Perm(w), applied to a string w, is all strings that can be constructed by permuting the symbols of w in any order. For example, if w= 101, then Perm(w) is all strings with two l's and one 0, i.e., Perm(w) = {101, 110, 011). If L is a regular language, then Perm(L) is the union of Perm(w) taken over all w in L. For example, if L is the language L(0*1*), then Perm(L) is all strings of 0's and 1's, i.e., L((0+1)*). If L is regular, Perm(L) is sometimes regular, sometimes context-free but not regular, and sometimes not even context-free. Consider each of the following regular expressions R below, and decide whether Perm(L(R)) is regular, context- free, or neither: 1. (01)* 2.0*+1* 3. (012)* 4. (01+2)* a) Perm(L(0*+1*)) is context-free but not regular. O b) Perm(L((01+2)*)) is context-free but not regular. c) Perm(L((01+2)*)) is not context-free. O d) Perm(L((01)*)) is regular.
In this work, we ask you to design a deterministic Finite Automaton (FA) to recognise arithmetic expressions. When we say arithmetic expression, we mean a kind of expression you can type in a very basic desk calculator. That is, neither variables nor brackets are allowed. It contains only numbers and four arithmetic operators, +, -, *, and /. The following are some examples of arithmetic expression: 1. Any number string with or without signs - e.g. 3, -1, +10, 3.14, -0.70 and 099. 2. Number strings mixed with arithmetic operators e.g. 3+5, -1+2*3, 7/10-0.7, and -1.4-+8.2. An example of FA diagram for recognising a non- negative integer is given below. You may use it as a start point. You need to add a few more states and transitions to handle numbers with decimal point and signs (e.g. -5, +2, 0.21, -32.6, +99.05, but not the form 1.0E-3). Most importantly, you also need to add a few more things to deal with the arithmetic operators +, -, *, /. →start 0-9 digit 0-9