CS 21 Decidability and Tractability Winter 2024
Out: January 17
Due: January 24
Problem Set 2
Copyright By PowCoder代写 加微信 powcoder
Reminder: you are encouraged to work in groups of two or three; however you must turn in your own write-up and note with whom you worked. You may consult the course notes and the text (Sipser). The full honor code guidelines and collaboration policy can be found in the course syllabus.
Please attempt all problems. Please turn in your solutions via Gradescope, by 1pm on the due date.
1. For a positive integer i, let N(i) denote its decimal representation (the usual string we write when writing the number i, with no leading zeros). Let N′(i) denote the string N(i) written in reverse order (least-significant digit first). Show that the language
L = {N(i)#N′(i + 2) : i ≥ 1}
over the alphabet Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, #} is recognizable by a pushdown automata.
2. Give a simple description of the language generated by the following context-free grammar:
S → aSb|bSa|SS|ε
and prove that it does in fact generate that language. Once you know the language, the following hint may help with the proof: Let x be a string in the language. Prove that the shortest (non-empty) prefix of x that is also in the language cannot begin and end with the same symbol.
3. Show that CFLs are not closed under intersection. To do this you should come up with two CFLs A and B with the property that C = A ∩ B = {x : x ∈ A and x ∈ B} is not a CFL. State the languages you are using and then:
(a) Prove that A and B are CFLs.
(b) ProvethatC=A∩BisnotaCFL.
4. Ogden’s Lemma and non-context-free languages.
(a) Consider the language L = {aibjckdl : i = 0 or j = k = l}. Prove that L satisfies the conditions of the CFL Pumping Lemma. In other words, the CFL Pumping Lemma is incapable of proving that L is not a CFL (since we cannot derive a contradiction from the assumption that L is a CFL).
(b) The following is a strengthening of the CFL Pumping Lemma:
Lemma 2.1 (Ogden’s Lemma) If L is a CFL, then there exists a pumping length p such that for every w ∈ L of length at least p and every way of “marking” p or more positions in w, w can be written w = uvxyz such that:
• foralli≥0,uvixyiz∈L,and
• vy contains at least 1 marked position of w, and • vxy contains at most p marked positions of w.
Prove Ogden’s Lemma. Hint: assume L is given by a CFG in Chomsky Normal Form, and consider a parse tree for w in this grammar. Pick a path from the root to a marked descendant by always travelling to the child with the greater number of marked descendants, and find a repeated nonterminal on that path. It may be useful in the course of the proof to single out “branch nodes,” which are internal nodes whose left and right children both have marked descendants.
(c) Use Ogden’s Lemma to prove that the language L from part (a) is not a CFL.
5. Show that CFL’s are not closed under complement. (The complement of a language L ⊆ Σ∗ is L = Σ∗ − L.)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com