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

Venkatesh, What is the arbwnememmsmdbdbfbfjmfksmjejfnfnfnnrndmnfjfjfnrnkrkf... What is the arbwnememmsmdbdbfbfjmfksmjejfnfnfnnrndmnfjfjfnrnkrkfjfnfmkrjrbfbbfjfnfjruhrvrjkgktithhrbenfkiffnbr ki rnrjjdjrnrk bd n FBC..jcb?????????????????????????????????????????

Context free grammar, A context free grammar G = (N, Σ, P, S)  is in binary... A context free grammar G = (N, Σ, P, S)  is in binary form if for all productions A we have |α| ≤ 2. In addition we say that G is in Chomsky Normaml Form (CNF) if it is in bi

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

Boolean operations - class of recognizable languages, Theorem The class of ... Theorem The class of recognizable languages is closed under Boolean operations. The construction of the proof of Lemma 3 gives us a DFA that keeps track of whether or not a give

Operations on strictly local languages, The class of Strictly Local Languag... The class of Strictly Local Languages (in general) is closed under • intersection but is not closed under • union • complement • concatenation • Kleene- and positive

Automaton for finite languages, We can then specify any language in the cla... We can then specify any language in the class of languages by specifying a particular automaton in the class of automata. We do that by specifying values for the parameters of the

Constract Context free, constract context free g ={ a^n b^m : m,n >=0 and n... constract context free g ={ a^n b^m : m,n >=0 and n

Pumping lemma constant, a) Let n be the pumping lemma constant. Then if L i... a) Let n be the pumping lemma constant. Then if L is regular, PL implies that s can be decomposed into xyz, |y| > 0, |xy| ≤n, such that xy i z is in L for all i ≥0. Since the le

Example of finite state automaton, The initial ID of the automaton given in... The initial ID of the automaton given in Figure 3, running on input ‘aabbba' is (A, aabbba) The ID after the ?rst three transitions of the computation is (F, bba) The p

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