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

Arden''s theoram, proof of arden''s theoram proof of arden''s theoram

Project, can you plz help with some project ideas relatede to DFA or NFA or... can you plz help with some project ideas relatede to DFA or NFA or anything

What is chomsky''s classification of grammar, Explain the Chomsky's classif... Explain the Chomsky's classification of grammar

Find regular grammar : a(a+b)*(ab*+ba*)b, Find the Regular Grammar for the ... Find the Regular Grammar for the following Regular Expression:                    a(a+b)*(ab*+ba*)b.

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

Alphabets - strings and representation, A finite, nonempty ordered set will... A finite, nonempty ordered set will be called an alphabet if its elements are symbols, or characters. A finite sequence of symbols from a given alphabet will be called a string ove

Dddddddddddddd, wwwwwwwwwwwwwwwwwwww wwwwwwwwwwwwwwwwwwww

Project Management at the Phoenician, Ask question #Minimum 20 words accept... Ask question #Minimum 20 words accepted#

Turing machine, explain turing machine . explain turing machine .

Rubber, Rubber shortnote Rubber shortnote