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 = {0^m10ⁿ10^max(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.

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

Ask an Expert

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

Write your message here..

Related Questions

Turing machine, explain turing machine . explain turing machine .

Tuning machine, design a tuning machine for penidrome design a tuning machine for penidrome

Pendulum Swings, how many pendulum swings will it take to walk across the c... how many pendulum swings will it take to walk across the classroom?

Kleene Closure, 1. Does above all''s properties can be used to prove a lang... 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 acyclic paths through your graph, Give the Myhill graph of your au... 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

Prove the arden''s theorem, State and Prove the Arden's theorem for Regular... State and Prove the Arden's theorem for Regular Expression

Pendulum Swings, how many pendulum swings will it take to walk across the c... how many pendulum swings will it take to walk across the classroom?

Algorithm for the universal recognition problem, Sketch an algorithm for th... 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

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

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