Write up solutions to the follow problems in LaTeX(可以用 overleaf.com,免费的). Submit hw7.tex
1. Write a high-level description of a Turing machine that decides the language L={
2. Problem 3.7 Explain why the following is NOT a description of a legitimate Turing Machine 𝑀𝑏𝑎𝑑 = “On input
, a polynomial of variables 𝑥1,𝑥2,…,𝑥𝑘:
1. Try all possible settings of 𝑥1,𝑥2,…,𝑥𝑘 to integer values.
2. Evaluate p on all of these settings.
3. If any of these settings evaluates to 0, accept; otherwise reject.”
3. Problem 3.12 A Turing Machine with left reset is similar to an ordinary Turing machine, but the transition has the form
𝛿: 𝑄 × Γ→ 𝑄 × Γ × {𝑅, RESET }}
If 𝛿(𝑞,𝑎)=(𝑟,𝑏,RESET), when the machine is in state q reading a, the machine’s head jumps to
the left-hand end of the tape after it writes b on the tape and enters state r. Note that these machines do not have the usual ability to move the head one symbol to the left. Show that Turing machines with left reset recognize the class of Turing-recognizable languages.
4. Problem 3.15e Show that the collection of Turing-decidable languages is closed under the operation of intersection.
5. Problem 3.16b Show that the collection of Turing-recognizable languages is closed under the operation of concatenation.
6. Problem 3.2c.
7. Problem 3.8b. The following structure for numbered lists in LaTeX will be useful.
\begin{enumerate} \item First Item \item Second Item \end{enumerate}
8. Create a Turing machine in JFlap to duplicate the input string on the tape. Assume an alphabet of {a,b}. So if the start configuration is q0aba the ending configuration should be abaabaq1. Note that q0 is the starting state and q1 is some other state.
9. Create a Turing machine in JFlap that, starting on an empty string, counts in binary on the tape. After each value is computed the read/write head should return to the first blank at the right end of the number.The count will look like the following (- is a blank cell):
——-
—-0–
—-1–
—10–
—11–
–100–
–101–
–110–
–111–
-1000–
etc…
Notes: There will be steps in between the actual numbers where the tape does not represent the next binary number make sure the number is correct when the r/w head returns to the right end of the non-blank symbols.
10. Write an implementation level description (not in JFlap) of a Turing Machine that searches for a pattern string inside a text string. The language is
L = {p#t | p, t = {a,b}* and the string p appears somewhere in the string t}
Additionally, if the machine accepts, the read/write head should be left at the location in the text where the pattern was found.
11.
Problem 2.16. Show that the class of context-free languages is closed under the regular
operations, union, concatenation, and star.
12.
13. Problem 1.46 c.
14. Problem 1.47.
15.Problem 1.49.b
16. Problem 2.4 b,c,e.
2.30 a, d. Use pumping lemma to show that a,d, are not context free