CS 21 Decidability and Tractability Winter 2024
Out: January 31
Due: February 7
This is a midterm. You may consult only the course notes and the text (Sipser). You may not collaborate. The full honor code guidelines can be found in the course syllabus.
Copyright By PowCoder代写 加微信 powcoder
There are 5 problems on 2 pages. Please attempt all problems. Please turn in your solutions via Gradescope, by 1pm on the due date. Good luck!
1. Identify each of the following languages as either (i) regular, (ii) context-free but not regular, or (iii) not context-free. For each language, prove that your classification is correct, using the techniques we have developed in this course.
(a) L1 = {aibjcidj : i,j ≥ 0}. (b) L2 = {aibjcjdi : i,j ≥ 0}.
(c) L3 = {aibjck : i = j = k or i > 1000}.
2. Identify each of the following languages as either decidable or undecidable, and prove that your classification is correct, using the techniques we have developed in this course. Recall that for a context free grammar G, we denote by L(G) the language it describes, and similarly for a regular expression E, we denote by L(E) the language it describes.
(a) cfl-in-reg = {(G, E) : G is a CFG, E is a regular expression, and L(G) ⊆ L(E)} (b) reg-in-cfl = {(E, G) : G is a CFG, E is a regular expression, and L(E) ⊆ L(G)}
Hint: you may wish to use the fact that the intersection of a context free language and a regular language is context-free (Sipser problem 2.18).
3. Two (disjoint) languages L1 and L2 are called recursively separable if there is a decidable lan- guage D for which L1∩D = ∅ and L2 ⊆ D; they are recursively inseparable if no such decidable language D exists. Convince yourself that an undecidable language and its complement are recursively inseparable.
Consider the following languages:
L1 = {⟨M⟩ : M halts and accepts input ⟨M⟩}
L2 = {⟨M⟩ : M halts and rejects input ⟨M⟩}
Prove that L1 and L2 are recursively inseparable. Hint: your proof will probably involve
supplying a Turing Machine its own description as input.
4. A right-linear CFG is a context-free grammar in which every production has the form • A → xB, or
where A and B are non-terminals, and x can be any string of terminals. A CFG is linear if productions of the form A → Bx are allowed in addition to the two types of productions in a right-linear CFG.
(a) Prove that every language generated by a right-linear CFG is regular.
(b) Prove that every regular language is generated by some right-linear CFG.
(c) Give a linear CFG that generates the non-regular language over the alphabet Σ = {a, b}, L = {w : w is a palindrome},
and prove that your grammar indeed generates exactly L (i.e., prove that every string in L is generated by your grammar, and prove that every string generated by your grammar is in L).
5. Given a language L, define 3-IN-A-ROWL as follows: 3-IN-A-ROWL = {#x1#x2# · · · #xk# : k ≥ 0
andforsomei,xi ∈Landxi+1 ∈Landxi+2 ∈L.}
Prove that 3-IN-A-ROWL is RE if L is RE. Here the xi are strings over L’s alphabet, and # is a symbol that is not in L’s alphabet.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com