Explain informally the working of the machine m

Assignment Help Theory of Computation
Reference no: EM131058101

COSC1105/1107 - Computing Theory Assignment

EXERCISE 1: TURING MACHINES               

1. Consider the following Turing Machine M = (Q, Σ, Γ, #, δ, q0, F), where Σ = {1, 2, 3} is the input alphabet and Γ = {1, 2, 3, a, b, #} is the tape alphabet (# is the blank symbol):

1233_Figure.png

A transition of the form 1/a, R means that when the head is reading 1, M can legally write a and move right.

(a) Trace the computation of M on input string 11222233 by completing the following derivation (location of head is denoted by underlining the respective symbol):

q0#11222233# |- q1#11222233# |- q2#a1222233# |- ...

Is the input string accepted?

(b) Explain informally, the working of the machine M.

(c) Give the language L(M ) in set notation.

(d) Provide a grammar having 12 or less rules that accepts the same language as M. What type of grammar is it?

(e) What properties of formal languages would you use (and how) to formally prove that there is no NFA that 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.            

(g) We obtain Turing Machine M' by modifying M as follows: (a) replace transition 3/3, R from state q1  to q5  with transition b/b, R; and (b) delete loop transition 3/3, R in state q5. Give the language L(Mt) in set notation.

2. Show formally, by resorting to problem reduction, that the problem, of deciding whether a Turing machine halts on an input w where |w| is a multiple of 5, is undecidable.

EXERCISE 2: AUTOMATA

3. Let M1 = (Q, Σ, δ1, q0, F1) be the following finite state automaton defined over the alphabet Σ = {a, b, c, d}:  

1253_Figure1.png

Here, λ denotes the empty transition.

(a) You are told that the following DFA M2 = (Q2, Σ, δ2, q0, F2), built using the subset construction technique, is a deterministic equivalent version of automaton M1:

2125_Figure2.png

After careful analysis, you realise that M2 is incorrect: it is not a deterministic equivalent version of M1.

Construct a DFA M3 = (Q2, Σ, δ3, q0, F3), from M2, by only adding or removing transitions and toggling whether a state is final or not (but without changing the set of states and the initial state), such that L(M1) = L(M3). In addition, you are asked ensure that the transition function δ3 is total. You do not     need to provide a diagram of M3; just answer the following questions by interpreting transition functions as relations (e.g., (q0, c, q1) ∈ δ2, since δ2(q0, c) = q1):

i. What is δ32?

ii. What is δ23?

iii. What is F3\F2?

iv. What is F2\F3?

(b) What modifications are required in M1 in order to make it λ-free without altering its language?  Your resulting machine M4 = (Q, Σ, δ4, q0, F4) will still be non-deterministic. You can only remove λ transitions, add transitions over Σ, or toggle whether a state is final or not, you must not change the set of states and you cannot change the initial state. You do not need to provide a diagram of M4; just answer the following questions:

i. What is δ41?

ii. What is δ14?

iii. What is F4\F1?

iv. What is F1\F4?

4. Emma's Pumping Lemma Dilemma: For her job application to tutor CT, Emma has been asked to prove that L = {anbma2m+3n | m, n ≥ 1} is not regular. The night before it was due, she finally finished the proof, wrote it all down neatly, and went to bed. During the night, burglars came into her house with their dog, and the dog chewed up her proof. In an attempt to cover their tracks, the burglars tried to recreate the proof. They gathered    all the shreds they could find, but on some of them the ink had washed out from the dog's saliva, and so they couldn't read some parts of it.  Can you help them put the proof back together?  For each shred they found, they rewrote it on a piece of paper. If they couldn't rewrite it, they wrote different interpretations of what they thought it read onto different pieces of paper. Now they have many pieces of paper, but they don't know which    of them are correct and in which order they need to go. Help Emma's burglars.

There is one big piece that reads:

Reminder: the Pumping lemma states, that for any regular language L, there exists a pumping length k ∈ N, and for all w ∈ L, where |w| ≥ k, there exist substrings x, y, z ∈ Σ*, such that:

w = xyz

|y| ≥ 1

|xy| ≤ k

xy'z ∈ L, for all i ≥ 0.       

Here are the other pieces they've transcribed:

(a) Now consider w = akbka5k.

(b) Now consider w = abaaaaa.

(c) Thus w = akbka5k = xyz such that |xy| ≤ k and |y| ≥ 1.

(d) Then, it follows that w ∈ L (where m = n = 1) and |w| = 7 ≥ 1.

(e) Then, it follows that w ∈ L (where m = n = k) and |w| = 7k ≥ k.

(f) Consider now i = 1. Then, xy'z = xyz = aqarasbka5k = aq+r+sbka5k.

(g) Consider now i = 0. Then, xy'z = xy0z = xz = aqasbka5k = aq+sbka5k.

(h) So, it follows that x = a, y = b, and z = aaaaa. Clearly w = abaaaaa = xyz.

(i) Assume that L is regular. Then, there exists a k ∈ N as per the Pumping Lemma.

(j) Consider now i = 2. Then, xy'z = xyyz = abbaaaaa. It is then clear that xy'z ∉ L.

(k) Now, because q + r + s = k and r ≥ 1, we know that q + s ≠ k, and therefore, xy'z ∉ L.

(l) Thus we have a contradiction: our assumption (that L is regular) must be blue and L is true.

(m) Now, because q + r + s = k and r ≥ 1, we know that aqaras = ak, and therefore, xy'z ∈ L.

(n) So, according to the Pumping lemma, there exist substrings x, y, z ∈ Σ* such that (1)-(4) hold.

(o) Thus we have a contradiction: our assumption (that L is regular) must be false and L is not regular.

(p) So, it follows that x = aq, y = ar, z = asbka5k, where q + r ≤ k, r ≥ 1, s ≥ 0, and q + r + s = k.

You need not write out the entire proof, just provide the corresponding letters in the correct order as a word. For example, the word badf denotes the proof built from statements (b), (a), (d), and (f) in that exact order. And remember:  the burglars wrote down multiple different interpretations of the same piece of the proof, so not all of these will be necessary or correct. However, all necessary pieces are listed above.

5. Prove that L = {amb2man | m, n ≥ 0} is not regular.         

6. Show that the language L2 = {a, b}*\{amb2man|m, n ≥ 0} is not regular. For this part, you can rely on the   fact that L, from the previous question, is not regular.

7. Show that the language L3 = {an | n ≥ 0, n ≠ 3 and n ≠ 6} is regular.        

EXERCISE 3-       

8. Prove mathematically that f (n) = 10n3 + 20n2 + 30 ∈ O(n4), for n ≥ 0.  

9. Suppose you are studying the computational complexity of a given problem X. It is known that the boolean satisfiability  problem  can  be  reduced  to  X  in  polynomial  time.  In  addition,  it  is  known  that  problem  X  is  in class PSPACE, as somebody has developed an algorithm for X that is guaranteed to consume no more than  polynomial amount of space. How would you prove that:

(a) X is NP-COMPLETE.

(b) X is PSPACE-Complete.

Observe that you do not need to develop any proof, but just explain briefly what task would you do.

10. Let X1 and X2 be two decision problems.  Suppose it is known that X1 is NP-COMPLETE. Suppose further that there exists an exponential reduction of problem X1 into problem X2, that is, there exists a function f: X1 → X2, whose implementation runs in exponential time, such that for any given instance x1 of X1 the answer to x1 is "Yes" for problem X1 if and only if the answer to f (x1) is "Yes" for problem X2. What can be said about the computation complexity of the problem X2. Is X2 NP-HARD? Explain in one or two paragraphs.

EXERCISE 4-       

11. Explain the phase transition phenomenon observed in 3-SAT.

You're expected to submit between 400 and 500 words (excluding references).

Think of it, as if you were hired to write a textbook for Computer Science undergraduates who are taking Computing Theory.

Besides providing enough technical information, your text needs to be enjoyable to read (or else the book will    not sell well!). Make sure you use multiple paragraphs, correct English grammar and spelling, and language of appropriate formality with an adequate flow.

You must not copy and paste a single sentence from the web (this includes Wikipedia).  Note that copied sentences are trivial to identify, so you should re-phrase in your own words whatever you read. You should also reference the material you used for your research.

Finally, we strongly recommend you proof-read your text, reflect on whether the reader (e.g., a fellow student) would be satisfied with what you wrote and revise accordingly.

Reference no: EM131058101

Questions Cloud

Appreciated or devalued against the mark : Assume that a bank has assets located in London worth £150 million on which it earns an average of 8 percent per year. The bank has £100 million in liabilities on which it pays an average of 6 percent per year. The current spot exchange rate is £1..
What are the goals of managerial accounting : How have the terms minority and majority evolved during your lifetime? How is this supported or negated through your reading of this week's American minority writers? Please share your impressions from the reading, include a quote, and, perhaps, a..
Themes and patterns about civil disobedience : read two articles: Search for common themes and patterns about civil disobedience. Do you think that civil disobedience is a valid way to change in society? Defend your position. Need to cite two articles.
Show that every 3nf schema is in 2nf : Show that every 3NF schema is in 2NF. (Hint: Show that every partial dependency is a transitive dependency.)
Explain informally the working of the machine m : Explain informally, the working of the machine M. Give the language L(M ) in set notation. Provide a grammar having 12 or less rules that accepts the same language as M. What type of grammar is it
Create a portfolio consisting of shares : You want to create a portfolio consisting of shares in Star plc plus a risk-free asset. You would like this portfolio to have the same beta as the market. What proportion of your money should you invest in each asset?
Critically explain the three forms of restructure : Comment on restructure and competitive performance issues, in relation to this area of the theory - development and application of skills and expertise individually enabling constructive engagement with challenges of restructure, its advantages and..
Find the arbitrage-free price of the call option : The one-period risk-free rate at which investors can borrow and lend is 5% per year. A European call option on this stock that expires in one year has an exercise price of £22. (i) Use the single period binomial option pricing model to find the arb..
Extension of the spring due to suspended weight : 1. A weight of 50 N is suspended from a spring of stiffness 5000 N/m and is subjected to a harmonic force of amplitude 40 N and frequency 4 Hz. Find: (a) The extension of the spring due to suspended weight.

Reviews

Write a Review

 

Theory of Computation Questions & Answers

  Define predicate combinations

Define predicate combinations which find the number of combinations K of up to N numbers. Validate your predicate with the subsequent test:

  Propositional and predicate logic

Write down a structural induction principle for the PlayTree free type

  Left recursive ebnf grammar into non-left recursive grammer

left recursive EBNF grammar into an equivalent non-left recursive grammer

  Discuss the process you used in making the decision

Discuss the process you used in making the decision. What ethical theory best reflects the foundation you used to make the decision.

  1 what are the problems in the performance appraisal system

1 what are the problems in the performance appraisal system of arrow electronics?2 if you were the ceo of arrow

  Prove by telescoping that tn cnlgn cn under the given

prove by telescoping that tn cnlgn cn under the following conditiontn c if n 1tn 2tn2 cn if n gt

  Construct an finite automata that accepts all binary strings

Construct an FA (finite automata) that accepts all binary strings with an even number of 0's and the number of 1's is a multiple of 3.Provide the answer of given question and also give details.

  Topicthe enhancement of communication process using a

topicthe enhancement of communication process using a particular computer device or software application by the

  The challenges of antonios wayfive basic goals often

the challenges of antonios wayfive basic goals often referred to as the backbone of antonios way were posted in

  Create standard 1-tape turing machine to calculate function

Create a standard 1-tape Turing machine M to calculate the function sub3. Specifically, calculate sub3 of a natural number represented in binary.

  Normal 0 false false false en-us x-none

normal 0 false false false en-us x-none x-none

  Is the given grammar left or right recursive

Is the given grammar left or right recursive - describe these in detail because I am having a hard time trying to figure this all out.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd