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

  Finite-state machine design

Create a finite-state machine design to turn your FPGA development board into a simple programmable music box.

  Redundant sequence identi cation

Redundant sequence identi cation

  Compute a shortest superstring

Dynamic programming algorithm to compute a shortest superstring.

  Propositional and predicate logic

Write down a structural induction principle for the PlayTree free type

  Design a syntactic analyzer

Design a syntactic analyzer for the language specified by the grammar

  Design unambiguous grammar to parse expressions

Write a program would read two numbers and then print all numbers between the first and the second, inclusive. Design unambiguous grammar to parse expressions

  Consider a logic function with three outputs

Consider a logic function with three outputs,  A ,  B , and  C , and three inputs,  D ,  E , and  F . The function is defined as follows:  A  is true if at least one input is true,  B  is true

  Considering a single programmed operating system

Considering a single programmed operating system, what is the minimal total time required to complete executions of the two processes? You should explain your answer with a diagram.

  How to construct an nfa

Give a construction that assumes you are given a DFA for L and show how to construct an NFA (with or without ε-moves) to recognize sort(L).

  Equivalence classes to construct minimal dfa for language

How many equivalence classes does this relation have and what are they? Use these equivalence classes to construct the minimal DFA for the language.

  Impact of moore-s law on data center costs

Discuss the impact of Moore's law on data center costs on such things as servers and communications equipment. List at least 3 steps or recommendations your data center can take to offset some or all of the effect of Moore's law.

  Problem encountered in statements in predicate logic

How the problem would be encountered in attempting to represent the following statements in Predicate logic. it should be possible to: John only likes to see French movies.

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