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
Define the following concept with an example: a.    Ambiguity in CFG b.    Push-Down Automata c.    Turing Machine

what are composition and its function of gastric juice

All that distinguishes the de?nition of the class of Regular languages from that of the class of Star-Free languages is that the former is closed under Kleene closure while the lat

Normal forms are important because they give us a 'standard' way of rewriting and allow us to compare two apparently different grammars G1  and G2. The two grammars can be shown to

We got the class LT by taking the class SL and closing it under Boolean operations. We have observed that LT ⊆ Recog, so certainly any Boolean combination of LT languages will also

Ask queyystion #Minimum 100 words accepted#

The SL 2 languages are speci?ed with a set of 2-factors in Σ 2 (plus some factors in {?}Σ and some factors in Σ{?} distinguishing symbols that may occur at the beginning and en

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


Find a regular expression for the regular language L={w | w is decimal notation for an integer that is a multiple of 4}