Construct a deterministic one way infinite single tape

Assignment Help Theory of Computation
Reference no: EM131226673

Construct a deterministic one way infinite single tape Turing machine that accepts the language { w | w in {x, y, z}* such that the number of x's in w < the number of y's in w and ((the number of x's in w divides the number of z's in w) or (the number of z's in w divides the number of x's in w)) }.

You may not make use of the fact that JFLAP has blank spaces to the left of the input. And you may not use blocks for this Turing machine. And finally, you can only use the left and right tape head moves (that is, do not use the stay directive).

Since JFLAP does not specifically have a reject state, you can either have a state that you transition to that has no outgoing transitions or you can simply leave off transitions that can never reach the accept state after taking, either will cause your Turing machine to reject the input.

My Turning machine has 31 states, but it appears that it could be reduced to 28 states or less, since I have two accept states and two reject states (states that go nowhere).

My implementation does the following:

1) Inserts a $ in front of the input string to mark the left end of the tape

2) As part of inserting the $, it rejects if the input consists of only y's

3) Verify that the number of x's < the number of y's 1. If not, reject

4) Check if x's = z's - if so, accept the input

     1. If the number of x's < z's - relabel x's as b's and z's as a's

     2. If the number of x's > z's - relabel x's as a's and z's as b's

5) Verify that the number of b's divides the number of a's

     1. If it does, accept

     2. If it doesn't, reject

Reference no: EM131226673

Questions Cloud

Describe an effective retention process : Explain why retention processes are vital in healthcare workforce planning.
Require different types of magical components : Awesome Optimizing Wizard that you are, Dumbledore has approached you to make wands for the wizarding community. Dumbledore would like for you to make quantities of two types of wands that require different types of magical components. Problem Write ..
Give the definition of stationarity in strong and weak sense : Give the definition of stationarity in strong and weak sense. Are the following processes stationary? Why? White noise (give the definition), Random walk (give the definition), MA(n) process (give the definition). How to test stationarity of an empir..
What is provinces position on physician assisted suicide : What is your state's or province's position on physician-assisted suicide? - Does your state or province differ from others? If so, why?
Construct a deterministic one way infinite single tape : Construct a deterministic one way infinite single tape Turing machine that accepts the language { w | w in {x, y, z}* such that the number of x's in w
Promote communication skills among adolescents : Develop a 10- to12- slide PowerPoint Presentation designed for training the staff at a local high school. The PowerPoint Presentation should focus on strategies that promote communication skills among adolescents.
Organizational restructuring and hiring plan : Investigate the current state of the HR department, employee issues with benefits, and ethical issues. Include the following: 1. Organizational restructuring and hiring plan for the HR department.
Prepare a partial income statement : Prepare a partial Income Statement for 2015 beginning with adjusted net income from continuing operations. Include all necessary earnings per share information assuming ABC Corp had 100,000 common stock shares outstanding throughout the year
Diagnosing poor performance problems : In what ways might you bring other principles into the class? Also, discuss how you would go about diagnosing poor performance problems. List several factors you would consider.

Reviews

Write a Review

 

Theory of Computation Questions & Answers

  Design and draw the state diagram

Design and draw the state diagram (graph-representation) of a deterministic finite-state automata that recognizes the language generated by the grammar

  Question 1show via chains of equivalences that the

question 1show via chains of equivalences that the following propositions are tautologies.a p and q rarr p harr qb p or

  Why arebinary numbers used in digital systems

Digital Systems and Switching Circuits,and answer the following study questions: What is the basic difference between analog and digital systems?

  Satisfy the properties - reflexive and symmetric

For the relations below, explain why the relation does or does not satisfy each of the properties reflexive,symmetric, antisymmetric, and transitive.

  1 discuss your assumptions and beliefs as a leader discuss

1. discuss your assumptions and beliefs as a leader. discuss how these have changed or evolved while studying business

  Task 1 managing meetingswhat are symptoms of groupthink

task 1 managing meetingswhat are symptoms of groupthink and how can you assure groupthink will not become a problem in

  Rahman s a 2006 lsquoattitudes of malaysian teachers toward

rahman s. a. 2006 lsquoattitudes of malaysian teachers toward a performance-appraisal system journal of applied social

  Give context-free grammars that generate languages

Give context-free grammars that generate the following languages - Transform the following grammar into Chomsky normal form

  Produce a system sequence diagram consistent

Produce a system sequence diagram consistent with the normal flow detailed in the full use case description.

  Create a program that makes an object

Create a class named Pet, after creating the class, create a program that makes an object of the class and prompts the user to enter the name, type, and age of his pet.

  Define the predicate successor

Define the predicate Successor (Year) giving the solution as the first successor to the crown for the year specified. To do this, use the predicates born(X, Year), died(X, Year), male(X).

  Explain the phase transition phenomenon

Explain the phase transition phenomenon observed in 3-SAT - 'What can be said about the computation complexity of the problem X2. Is X2 NP-HARD

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd