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

Construct a regular expression, Given any NFA A, we will construct a regula... Given any NFA A, we will construct a regular expression denoting L(A) by means of an expression graph, a generalization of NFA transition graphs in which the edges are labeled with

Convert chomsky normal form into binary form, Suppose G = (N, Σ, P, S) is a... 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

Myhill graph of the automaton, Exercise:  Give a construction that converts... Exercise:  Give a construction that converts a strictly 2-local automaton for a language L into one that recognizes the language L r . Justify the correctness of your construction.

Turing machine, explain turing machine . explain turing machine .

Strictly local languages, While the SL 2 languages include some surprising... While the SL 2 languages include some surprisingly complex languages, the strictly 2-local automata are, nevertheless, quite limited. In a strong sense, they are almost memoryless

Formal languages and grammar, The universe of strings is a very useful medi... The universe of strings is a very useful medium for the representation of information as long as there exists a function that provides the interpretation for the information carrie

Transition and path functions, When an FSA is deterministic the set of trip... When an FSA is deterministic the set of triples encoding its edges represents a relation that is functional in its ?rst and third components: for every q and σ there is exactly one

Equivalence of nfas and dfas, In general non-determinism, by introducing a ... In general non-determinism, by introducing a degree of parallelism, may increase the accepting power of a model of computation. But if we subject NFAs to the same sort of analysis

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

Multiple instruction single data stream, short application for MISD short application for MISD