CS375-HW8-2023f_Akwa

pdf

School

Bluegrass Community and Technical College *

*We aren’t endorsed by this school

Course

170

Subject

Computer Science

Date

Nov 24, 2024

Type

pdf

Pages

7

Uploaded by DukeEnergyFish

Report
CS375 Homework Assignment 8 (40 points) Due date: 11/29/2023 1. (9 points) To move an input string over {a, b} to the right two cells position , we can use the TM specified in Question 6 of HW7 twice. It is also possible to move a string to the right two cells position directly. Such a TM has the following states: State 0: the initial state State 1: indicates the TM carries an ‘a’ in its hand State 2: indicates the TM carries a ‘b’ in its hand State 11: indicates the TM carries ‘aa’ in its hand State 12: indicates the TM carries ‘ab’ in its hand State 10: indicates the TM carries ‘aɅ’ in its hand State 21: indicates the TM carries ‘ba’ in its hand State 22: indicates the TM carries ‘bb’ in its hand State 20: indicates the TM carries ‘bɅ’ in its hand State halt: the last state Fill out the blanks in the following instruction set to make it an instruction set for such a TM. (0.5 point for each blank) 11 12 10 21 22 20
2. (4 points) The following is the instruction set of a Turing machine (TM) that accepts the language { ? 𝑛 ? 𝑛 | n ∈ N }. 11 12 10 21 22 20 11 12 10 21 22 20
This TM does not accept the string aaabb . Why? Put your reason in the following box. You can not simply say the number of a’s is not the same as the number of b’s. The TM cannot tell if the number of a’s is not the same as the number of b’s. It would reject a string only if it reaches a point that it cannot proceed any further and the state is not the ‘ halt ’ state. 3. (9 points) The following is the instruction set of a Turing machine (TM) that computes the sum of 2 and a given natural number represented as a binary string. The read/write head of the TM starts at the right end of the given natural number and halts at the left end of the output string. The start state of the TM is 0. Following the successful marking of the first two a's with X and the first two b's with Y, the read-write head will locate a b and mark the final an in the middle with X. Nevertheless, the string contains no more bs, thus the read- write head ends on a κ in state 1 with no guidance on what to do. The execution halts and the input string "aaabb" is rejected in the absence of a command for such a combination.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
In the following, fill out the blanks in the following sum computation process for the given natural number 54 (= 110110 2 ). For each step, put the instruction to be used for that step in the blank on the left side, and fill out the blank(s) in the I/O tape on the right side. (1 point each blank) (0,1,1,L,1) (1,1,0,L,1) 1
From this point on, every digit read by the TM will be kept the same until the left end of the string is reached. 4. (18 points) Given an integer say 47, to find the sum of 47 with 8 in binary form (see the figure below), we can use the TM designed in slides 89-100 of the notes “Turing Machines and Equivalent Models I” twice to find the result. A more effective way is to design a TM to do the addition with 8 directly. Such a TM can be designed by extending the TM designed in slides 89- 1 (1,1,0,L,1) (1,0,1,L,2) 1 (2,1,1,L,2) 2
100 of the notes “Turing Machines and Equivalent Models I”. The TM has 14 instructions and 6 states: 0, 1, 2, 3, 4 , and halt . Five instructions of such a TM have been given in the first table below. Fill out the remaining blanks of the first table and also blanks in the second and third tables to show the remaining instructions of the TM (you have to use your own text boxes here) and then fill out the blanks in the following chart to make it a complete state transition diagram for this TM. Make sure the instructions you choose fit into the diagram naturally and logically. In the diagram, state H means the ‘ Halt ’ state. You have to use your own text boxes here too. (1 point each blank) • Solutions must be typed (word processed) and submitted both as a pdf file (2,0,0,L,3) (2,1,1,L,3) (2,^,0,L,3) (3,0,1,L,4) (3,1,0,L,3) (3,^,1,S,halt) (4,0,0,L,4) (4,1,1,L,4) (4,^,^,R,halt) 0 0, L ^ 0, L 1 0, L 0 1,L 0 0,L 1 1,L 1 1, L 1 1, S ^ ^,R
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
and a word file to Canvas before 23:59 on 11/29/2023. • Don’t forget to name your files as CS375_2023f_HW8_LastName.docx / CS375_2023f_HW8_LastName.docx

Related Documents

Week 7 refelection computer class.docx
CS 4402 DF week 1 (4).pdf
WGU C172 Network and Security (18).pdf
Examen_ [AAB01] Cuestionario 4_ Identifica los principios y conceptos relacionados a Control de Acce
Assignment3.jpg
Learning Guide Unit 7_ Reading Assignment.pdf
Assignment 2.pdf
Learning Guide Unit 7_ Learning Journal.pdf
WA Worksheet_The Method.docx
image (1).jpg
Unit 2 Milestone-24.pdf
93.1- Self Quiz 8 (Quiz · 5 Questions).pdf
Recommended textbooks for you
Text book image
C++ for Engineers and Scientists
Computer Science
ISBN:9781133187844
Author:Bronson, Gary J.
Publisher:Course Technology Ptr
Text book image
Programming Logic & Design Comprehensive
Computer Science
ISBN:9781337669405
Author:FARRELL
Publisher:Cengage
Text book image
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
Text book image
EBK JAVA PROGRAMMING
Computer Science
ISBN:9781337671385
Author:FARRELL
Publisher:CENGAGE LEARNING - CONSIGNMENT
Text book image
Microsoft Visual C#
Computer Science
ISBN:9781337102100
Author:Joyce, Farrell.
Publisher:Cengage Learning,
Text book image
Programming with Microsoft Visual Basic 2017
Computer Science
ISBN:9781337102124
Author:Diane Zak
Publisher:Cengage Learning
SEE MORE TEXTBOOKS
Recommended textbooks for you
Text book image
C++ for Engineers and Scientists
Computer Science
ISBN:9781133187844
Author:Bronson, Gary J.
Publisher:Course Technology Ptr
Text book image
Programming Logic & Design Comprehensive
Computer Science
ISBN:9781337669405
Author:FARRELL
Publisher:Cengage
Text book image
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
Text book image
EBK JAVA PROGRAMMING
Computer Science
ISBN:9781337671385
Author:FARRELL
Publisher:CENGAGE LEARNING - CONSIGNMENT
Text book image
Microsoft Visual C#
Computer Science
ISBN:9781337102100
Author:Joyce, Farrell.
Publisher:Cengage Learning,
Text book image
Programming with Microsoft Visual Basic 2017
Computer Science
ISBN:9781337102124
Author:Diane Zak
Publisher:Cengage Learning
SEE MORE TEXTBOOKS