Reference no: EM13937967
1. Consider the following Turing MachineM = (Q, !,#,^, !, q0, F), where^ = {7, 8, 9} and! = {1, 2, 7, 8, 9,#}:Here, a transition of the form 9/1,R means that when the head is reading 9, M can legally write 1 and move right. Blank is denoted by #.
(a) Trace the computation ofM on input string 99888877 by completing the following derivation (the location [2] of the head is denoted by underlining the respective symbol):
q0#99888877# ` q1#99888877# ` q2#19888877# ` · · ·
Is the input string accepted?
(b) Explain informally, the working of the machine M. [4]
(c) Give the language L(M) in set notation. [3]
(d) Provide a grammar having 10 or less rules that accepts the same language as M. What type of grammar [6] is it?
(e) What properties of formal languages would you use (and how) to formally prove that there is no NFA that [4] can accept the language L(M). Explain briefly (note: you do not need to actually do any proof).
(f) Does there exist a PDA that accepts L(M)? Briefly explain your answer in one short sentence. [3]
(g) We obtain Turing Machine M0 by modifying M as follows: (a) replace transition 7/7,R from state q1 to [3] q5 with transition 2/2,R; and (b) delete loop transition 7/7,R in state q5. Give the language L(M0) in set notation.
2. Show formally, by resorting to problem reduction, that the problem, of deciding whether a Turing machine halts [8] on some input of length divisible by 3, is undecidable.
|
Calculate the front-end load
: The World Income Appreciation Fund has current assets with a market value of $11.2 billion, 420 million shares outstanding, and a current market price quotation of $28.08. Calculate the front-end load.
|
|
Design a combinational logic function
: You are required to design a combinational logic function with 4 inputs (P, Q, R, S) and a single output (Z). Whenever the minterm value of the inputs (PQRS) matches one of the digits in your SID the function output will be a don't care. Otherwise..
|
|
What earnings per share does cook report before expansion
: What earnings per share does Cook report before the expansion? What earnings per share will Cook report if the proposed expansion is undertaken?
|
|
What is the maximum dollar purchase you can make
: You have $30,000 and decide to invest on margin. If the initial margin requirement is 60 percent, what is the maximum dollar purchase you can make?
|
|
Less rules that accepts the same language
: Consider the following Turing MachineM = (Q, !,#,^, !, q0, F), where^ = {7, 8, 9} and! = {1, 2, 7, 8, 9,#}:Here, a transition of the form 9/1,R means that when the head is reading 9, M can legally write 1 and move right. Blank is denoted by #.
|
|
Make the presidents replacement economically advantageous
: In 2006, Violet Rose Computer Corporation purchased a new quality inspection system for $550,000. The estimated salvage value was $50,000 after 10 years. Currently the expected remaining life is 7 years with an AOC of $27,000 per year and an estimate..
|
|
What is the expected return of your portfolio
: Stock J has a beta of 1.25 and an expected return of 13.41 percent, while Stock K has a beta of 0.8 and an expected return of 10.35 percent. You want a portfolio with the same risk as the market. What is the portfolio weight of each stock? What is th..
|
|
Create a portfolio with an expected return
: You have $252,000 to invest in a stock portfolio. Your choices are Stock H, with an expected return of 14.2 percent, and Stock L, with an expected return of 10.3 percent. If your goal is to create a portfolio with an expected return of 12.1 percent, ..
|
|
Show the effects of the previous transactions
: Show the effects of the previous transactions on the accounting equation using the following format. Assume the note payable is to be repaid within the year.
|