Assignment 8

docx

School

Portland Community College *

*We aren’t endorsed by this school

Course

464

Subject

Computer Science

Date

Nov 24, 2024

Type

docx

Pages

10

Uploaded by ProfessorIceCat10

Report
Answer 1:
Answer 2 : Turing machine that computes the function f(x) = 2x + 3, where x is a positive integer represented in unary: States:Q = {q0, q1, q2, q3, q4} Input symbols: Σ = {1} Output symbols: Γ = {1, B} Tape blank: B Start state:q0 Accept state: q4 Transition function: δ | State | Input | Output | Next state | |---|---|---|---| | q0 | 1 | 1 | q1 | | q1 | 1 | 1 | q2 | | q2 | 1 | B | q3 | | q3 | 1 | B | q4 | | q4 | | | q4 |
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
State Input Output Next State q0 1 1 q1 q1 1 1 q2 q2 1 B q3 q3 1 B q4 q4 1 q4 Description: The Turing machine starts in state q0. It reads the input symbol 1 and writes a 1 to the tape. It then moves to state q1. In state q1, the Turing machine reads the input symbol 1 and writes another 1 to the tape. It then moves to state q2. In state q2, the Turing machine reads the input symbol 1 and erases it from the tape. It then moves to state q3. In state q3, the Turing machine reads the input symbol 1 and writes a B to the tape. It then moves to state q4. The Turing machine remains in state q4 until the end of the input tape is reached. At this point, the output tape will contain the binary representation of 2x + 3, where x is the input integer. Screenshot:
Test cases:
* Input: 11 (x = 2) * Output: 1111111 (f(2) = 7) * Input: 111 (x = 3) * Output: 11111111 (f(3) = 9) * Input: 1111 (x = 4) * Output: 111111111 (f(4) = 11) Answer 3 : Create a Turing machine that when started anywhere on the tape will halt if and only if there is a 0 somewhere on the tape. You won't be able to test this one in JFLAP, since it only lets you enter a single input string as the starting configuration of the tape. （ For this problem, the tape can start with 0s and 1s scattered anywhere on the tape - they do not have to be contiguous. Any permutation of 0s, 1s and blanks is a possible starting configuration. ）
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
states: {q0,q1,q2,q3} input alphabet: {a,b} tape alphabet: {0,1,a,b,□} blank symbol: □ initial state: q0
final states: {q3} transitions: δ(q2,□) = (q3,□,R) δ(q0,b) = (q1,□,R) δ(q1,b) = (q0,□,R) δ(q0,□) = (q2,0,L) δ(q0,a) = (q1,□,R) δ(q1,a) = (q0,□,R) δ(q1,□) = (q2,1,L) Description: The Turing machine starts in state q0 and begins searching for a 0 on the tape. It reads the current input symbol and writes it back to the tape. It then moves to the next state based on the input symbol: * If the input symbol is a 0, the Turing machine moves to state q2.
* If the input symbol is a 1 or a blank, the Turing machine moves to state q1. If the Turing machine reaches state q2, it has found a 0 on the tape and it halts. If the Turing machine reaches state q3, it has reached the end of the tape and has not found a 0. In this case, the Turing machine halts and rejects the input. Proof: The Turing machine will halt if and only if there is a 0 on the tape. If: If there is a 0 on the tape, the Turing machine will eventually reach state q2 and halt. Only if: If the Turing machine halts, it must have reached state q2. The only way to reach state q2 is to find a 0 on the tape. Test cases: Input: 11111 Output: □□□□□ Input:01111 Output: 0□□□□
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
Input: 11110 Output: 1□□□0 Input: 0□1□1 Output: 0□□□0 Input: □□110 Output: □□□00 In each of these test cases, the Turing machine halts if and only if there is a 0 on the tape.

Related Documents

Multimedia systems.edited.edited.docx
Lab3+-+CEG3585-S20.pdf
Digital Photography I Unit 4 Exam.pdf
Tarea #3 - Densidad.docx
Long Quiz 004 - (2).png
Unit 6 Homework Part to Whole Analysis RUBRIC.doc
1ST-quarter-test (1).docx
Assignment 4 (page 1 of 8).pdf
CelsiusTemperature.txt..cpp
W03 QUIZ IPA.docx
Screenshot 2023-11-11 at 12.48.25 PM.png
CIS123_2.4_Using_Standard_Non-Standard_Python_Libraries_Implement_Functions_Corey_Adams.py
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
Principles of Information Systems (MindTap Course...
Computer Science
ISBN:9781285867168
Author:Ralph Stair, George Reynolds
Publisher:Cengage Learning
Text book image
Fundamentals of Information Systems
Computer Science
ISBN:9781305082168
Author:Ralph Stair, George Reynolds
Publisher:Cengage Learning
Text book image
Fundamentals of Information Systems
Computer Science
ISBN:9781337097536
Author:Ralph Stair, George Reynolds
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
Principles of Information Systems (MindTap Course...
Computer Science
ISBN:9781285867168
Author:Ralph Stair, George Reynolds
Publisher:Cengage Learning
Text book image
Fundamentals of Information Systems
Computer Science
ISBN:9781305082168
Author:Ralph Stair, George Reynolds
Publisher:Cengage Learning
Text book image
Fundamentals of Information Systems
Computer Science
ISBN:9781337097536
Author:Ralph Stair, George Reynolds
Publisher:Cengage Learning
SEE MORE TEXTBOOKS