Explanation of turing machine

Assignment Help Theory of Computation
Reference no: EM1380779

Question: Devise a Turing machine with input given in unary notation (i.e., a string of n 1's denotes the integer n, and numbers are delimited by 0's) such that the machine produces the following output:

0 if x is divisible by 4

1 if x is congruent to 1 modulo 4

2 if x is congruent to 2 modulo 4

3 if x is congruent to 3 modulo 4

Demonstrate the state table for the machine.

 

Reference no: EM1380779

Previous Q& A

  Findings is that average annual household spending

The U.S. Bureau of Labor Statistics released its Consumer Expenditures report in October 2008. Among its findings is that average annual household spending on food at home was $3,624.

  Illustrate risks also benefits of purchasing a home

Illustrate what is your recommendation as to risks also benefits of purchasing a home based on se considerations.

  Is it ethical to use design elements also special effects

Is it ethical to use design elements also special effects to persuade an audience. Explain why or explain why not. Please feel free to use an example.

  Determine if benefits of free trade outweigh drawbacks

Is it discrimination for a Chinese restaurant to only hire Chinese servers. Explain why or explain why not. Determine if benefits of free trade outweigh drawbacks also illustrate what could be done to address drawbacks.

  Hono golf is a manufacturer of golf products

Hono Golf is a manufacturer of golf products in Taiwan and China. One of the golf accessories it produces at its plant in Tainan Hsing, Taiwan, is plastic golf tees. The injector molder produces golf tees that are designed to have an average heigh..

  Question about perfect programming language

I have noticed that there are several languages, is this because no one language has all the main elements needed to be a perfect programming Language?

  Describe trends and recent events

Describe trends and recent events - how are things changing? Discuss the entity's relationship to international management

  Determines if benefits of free trade outweigh drawbacks

Determines if benefits of free trade outweigh drawbacks also illustrate what could be done to address drawbacks.

  Issue facing many states is whether to legalize casino

A major issue facing many states is whether to legalize casino gambling. Suppose the governor of one state believes that more than 55% of the state's registered voters would favor some form of legal casino gambling

  Illustrate what should a memo telling staff

Illustrate what should a memo telling staff illustrate what to do when they encounter problems, with business technology comprise.

Reviews

Write a Review

 

Similar Q& A

  Question about perfect programming language

I have noticed that there are several languages, is this because no one language has all the main elements needed to be a perfect programming Language?

  Rice-s theorem for enumerable or non-re

We know by rice's theorem that none of the following problems are decidable. However,are they recursively enumerable,or non-RE? IS L(M) infinite?

  Interpreting the regular expressions as languages

Show that the following identities hold for regular expressions over any alphabet: epsilon + R*R = R*. These should be done by interpreting the regular expressions as languages.

  Create standard 1-tape turing machine to calculate function

Create a standard 1-tape Turing machine M to calculate the function sub3. Specifically, calculate sub3 of a natural number represented in binary.

  Why every nonempty propositional clause itself satisfiable

Describe why every nonempty propositional clause, by itself, is satisfiable. Prove rigorously that every set of five 3-SAT clause is satisfiable, given that each clause mentions exactly three distinct variables.

  Design mealy fsm with the input a and output z

Design a Mealy FSM with the input A and an output Z. If 10101 shows up on A, then in same cycle 1 must show up on Z, else Z is 0.

  Write grammar for language consisting of strings

Write a grammar for the language consisting of strings that have n copies of the letter a followed by same number of copies of the letter b, where n>0

  Propositional and predicate logic

Write down a structural induction principle for the PlayTree free type

  Argue that the problem is np complete

Argue that the following prob is NP Complete. Given list of positive integers, u1,u2,...un (in binary representation) and asked if there is partition of this set into 3 subsets, each of which has same sum.

  If l recognized by dfa then language left half is regular

We showed to prove that if L can be identified by DFA then the language left half(L) = {x ∈ ∑*|∃y xy ∈ L and |x| = |y|} is also regular; here |x| means length of x.

  What ambiguity exists in the statement

Suppose f is a function that returns the result of reversing the string of symbols given as its input, and g. What ambiguity exists in the statement x?

  Design a syntactic analyzer

Design a syntactic analyzer for the language specified by the grammar

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