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

design a tuning machine for penidrome

how many pendulum swings will it take to walk across the classroom?

1. Does above all''s properties can be used to prove a language regular? 2..which of the properties can be used to prove a language regular and which of these not? 3..Identify one

Give the Myhill graph of your automaton. (You may use a single node to represent the entire set of symbols of the English alphabet, another to represent the entire set of decima

State and Prove the Arden's theorem for Regular Expression

how many pendulum swings will it take to walk across the classroom?

Sketch an algorithm for the universal recognition problem for SL 2 . This takes an automaton and a string and returns TRUE if the string is accepted by the automaton, FALSE otherwi

What is the Best way to write algorithm and construct flow chart? What is Computer? How to construct web page and Designe it?

how to prove he extended transition function is derived from part 2 and 3