What properties of formal languages would you use and how

Question

Question 1. Consider the following Turing Machine M = (Q, Γ, #, ∑, δ, q_o, 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 of M on input string 99888877 by completing the following derivation (the location [2) of the head is denoted by underlining the respective symbol):

q_o#99888877# |- q₁#29888877# |- q₂#12888877# |- .......

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 10 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 Al as follows: (a) replace transition 7/7, R from state q1 to q5 with transition 2/2 R; and (b) delete loop transition 7/7, R in state q5. Give the language L(M') in set notation.

Question 2. Show formally, by resorting to problem reduction, that the problem, of deciding whether a Turing machine halts on some input of length divisible by 3, is undecidable.

Question 3. Let M₁ = (Q, ∑, δ₁, so, F₁ ) be the following finite state automaton defined over the alphabet E = {a, b, c}:

Here, λ denotes the empty transition.

(a) You are told that the following DFA M₂ = (Q, ∑, δ₂, so, F₂), built using the subset construction technique, [Ill is a deterministic equivalent version of automaton M₁:

After careful analysis, you realise this machine is not entirely correct: it is not a deterministic equivalent version of M₁.

Construct a DFA M₃ = (Q, ∑, δ₃, so, F₃), from M₂, by only adding or removing transitions and toggling whether a state is final or not (but without changing the set of states), such that L(M₁) = L(M₃). You do not need to provide a diagram of M₃; just answer the following questions:

i. What is δ3 \ δ2?

ii. What is δ2 \ δ3?

iii. What is F3 \ F2?

iv. What is F2 \ F3?

(b) What modifications would you do to MI in order to make it A-free without altering its language? Your [71 resulting machine M4 = (Q, E, 84, so, F4) will still be non-deterministic. You can only add or remove transitions or toggle whether a state is final or not, but you must not change the set of states. You do not need to provide a diagram of M4; just answer the following questions:

i. What is δ4 \ δ1?

ii. What is δ1 \ δ4?

iii. What is F4 \ F1?

iv. What is F1 \ F4?

Question 4. Emma's Pumping Lemma Dilemma: For her job application to tutor CT, Emma has been asked to prove that L = {aⁿb^ma^m+n | 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.

Question 5. Prove that L = {a^mb^m+naⁿ | m, n ≥ 0} is not regular.

Question 6. Show that the language L₂ = {a, b}* \ (a^mb^m+naⁿ | m, n ≥ 01 is not regular. For this part, you can rely on the fact that L, from the previous question, is not regular.

Question 7. Show that the language L₃ = {aⁿ | n ≥ 0,n ≠ 5} is regular.

Question 8. Prove mathematically that f(n) = 7n³ + 30n² + 100 ∈ 0(n³), for n ≥ 0.

Question 9. Briefly explain whether the following statements are true or false (mere "true" or "false" answers will attract zero marks):

(a) If a program has polynomial space complexity, then it will take a maximum of polynomial time. What about the converse statement?

(b) If functions f and g are such, that f(n) ∈ 0(g(n)), then it has to be the case that f(n) ∈ (g(n)3).

(c) If t_M(n) is the time complexity of the Turing Machine Al from Exercise 1, Question 1, then:

i. t_M(n) ∈ 0(n).
ii. t_M(n) ∈ 0(n²).
iii. t_M(n) ∈ 0(2ⁿ).

Question 10. One technique to show that a decision problem is NP-hard, is to reduce a known NP-hard problem, such as 3SAT, to the problem of concern in polynomial time. Explain why it is fundamental that the reduction provided be indeed a polynomial time reduction. Also, state which Theorem in Sudkamp's book makes use of this requirement.

Question 11. Compare and contrast Mealy and Moore machines.

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. As such, you can safely assume the reader knows basic notions, such as what a Finite State Machine is.

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.