Reference no: EM131301497 , Length:
Turing Machine Construction and reductions
Please show the graph of the machine with all edges labeled and please provide a brief description of the purpose of the states in your machines. You must use JFLAP to construct your Turng Machines.
For each TM you build, please add a BRIEF English description of how it operates. Make your English decription as clear as possible! Please note - this one may take some time so please get going on it SOON.
1. Construct a TM that recognizes the non-CFL language L = {wcw | w is in (0+1)*} and halts on all inputs. Please briefly explain the purpose of each state of your machine. So, for example the string 1110c1110 IS in L but the string 0010c0110 is NOT.
2. Construct a TM that expects a string of 0's and 1's and replaces all 1's with 0's and all 0's with 1's. For example, if started with the string 01110110 then the machine would halt with 10001001 on the tape. If it was started with 0001 then it would halt with 1110.
3 Suppose you had a Deterministic Turing Machine that at some point was in a state q over a tape that is completely blank except for one cell which contains a #. If the read/write head is currently over a blank cell and you do not know where the # lies with respect to the current position then what would you need to do to move the read/write head so that it is over the # and in state p how would you accomplish this? Describe how your machine would work. You do not need to actually construct the machine simply describe how it would work. NOTE - the TM MUST be deterministic.
4. Solve the previous problem with a non-deterministic Turing machine. Explain how the machine would work and how it differs from the deterministic version.
For each of the following languages - tell me if the language is Recursive, RE, or NON-RE. Prove your answer either by describing the TM for the language or by performing a Turing reduction of the appropriate form.
5. L1={ <M1,M2> | L(M1) != L(M2) }
6. L2={ <M1,M2> | there exists a w such that w ∈ L(M1) and w ∈ L(M2) }
7. L3 = { <M> | 10001 ∈ L(M) }
|
Describe how a sub-band coder operates
: Down to what bit rate can we expect from a CELP coder without sacrificing too much voice quality/intelligibility?
|
|
Write up an assessment with walter and his grandmother
: Write up an assessment with Walter and his grandmother that incorporates and reflects the situation and his needs as presented in the interview. Please review the Assessment Chapter in the Woodside Book to include components of the Assessment Pha..
|
|
What types of investments will you purchase
: Summarize your reasoning for either investing or not investing to meet your goals.- If you decide to invest, how much will you invest each month? What types of investments will you purchase? Why?
|
|
Compute the net interest expense
: (a) Compute the net interest expense to bereported for this note and related swap transactions as of December 31, 2014. (b) Compute the net interest expense to bereported for this note and related swap transactions as of December 31, 2015.
|
|
Construct a tm that recognizes the non-cfl language
: Construct a TM that recognizes the non-CFL language L = {wcw | w is in (0+1)*} and halts on all inputs. Please briefly explain the purpose of each state of your machine. So, for example the string 1110c1110 IS in L but the string 0010c0110 is NOT.
|
|
What advantage might there be for employing older employees
: Does society need to rethink the traditional notion of retirement?What strategies can managers implement in an effort to manage their older employees effectively? Do you have any examples from where you work?What advantage might there be for employ..
|
|
Where would we use an interleaver and how does it work
: Often cells and cell site transmitter-antenna parameters are built around a signal level contour. What is the value of this contour in dBµ? Also give this dBµ value in dBm based on a 50 - Ω impedance at 850 MHz.
|
|
Net interest rate on the loan
: Explain how the company can use a forward rate agreement (FRA) to hedge the interest rate risk. Calculate the forward rate for the FRA. What is the payment to or from the firm if 6-month LIBOR is 1.85% in December, and what is the net interest rat..
|
|
Contractionary and expansionary monetary policy
: 1. Now that you know the difference between contractionary and expansionary monetary policy, imagine yourself as the Chairman of the Federal Reserve Board of Governors. Which monetary policy do you believe is more appropriate today and why?
|