Describe the algorithm and draw the transition diagram, Theory of Computation

1. Simulate a TM with infinite tape on both ends using a two-track TM with finite storage

2. Prove the following language is non-Turing recognizable using the diagnolization principle { (M, w) | TM M, starts with input w, does not halt}

3. Construct a TM for L = {w| w contains equal number of 0's and 1's} over {0,1} a) provide an algorithmic description b) draw the transition diagram

4. Consider a language L = {0m10n10max(m,n)| m, n>= 0}. Construct a TM that decides the language. Describe the algorithm and draw the transition diagram of the TM.

5. Given the following TM M, does M a) accept or b) reject on inputs w1 = 000 and w2=0000? Show the content of the input tape and positions of the head step-by-step.

1072_Describe the algorithm and draw the transition diagram.png

Posted Date: 3/20/2013 6:19:18 AM | Location : United States







Related Discussions:- Describe the algorithm and draw the transition diagram, Assignment Help, Ask Question on Describe the algorithm and draw the transition diagram, Get Answer, Expert's Help, Describe the algorithm and draw the transition diagram Discussions

Write discussion on Describe the algorithm and draw the transition diagram
Your posts are moderated
Related Questions
Let there L1 and L2 . We show that L1 ∩ L2 is CFG . Let M1 be a decider for L1 and M2 be a decider for L2 . Consider a 2-tape TM M: "On input x: 1. copy x on the second


proof ogdens lemma .with example i am not able to undestand the meaning of distinguished position .


Suppose G = (N, Σ, P, S) is a reduced grammar (we can certainly reduce G if we haven't already). Our algorithm is as follows: 1. Define maxrhs(G) to be the maximum length of the


Applying the pumping lemma is not fundamentally di?erent than applying (general) su?x substitution closure or the non-counting property. The pumping lemma is a little more complica

State & prove pumping lemma for regular set. Show that for the language L={ap |p is a prime} is not regular

Another way of representing a strictly 2-local automaton is with a Myhill graph. These are directed graphs in which the vertices are labeled with symbols from the input alphabet of

The objective of the remainder of this assignment is to get you thinking about the problem of recognizing strings given various restrictions to your model of computation. We will w