2-hw: Nonregular Languages and Context-free Languages CSE105SP20 Due: Sunday May 3 at 11:00PM (on Gradescope) The same homework policies apply as in 1-hw. Please see that assignment writeup for details about • Collaboration policy and group size. • Submission instructions. • Typed work. • Expectations for justification Reading and extra practice problems: Sipser Section 1.4, 2.2. Chapter 1 exercises 1.29, 1.30. Chapter 1 problems 1.49, 1.50, 1.51. Chapter 2 exercises 2.5, 2.7. Key Concepts: Pumping lemma, nonregular sets, pushdown automata (PDA), stack. 1. In class and in the reading so far, we’ve seen the following examples of nonregular sets: {0n1n | n ≥ 0} {0n1n | n ≥ 2} {0n1m | 0 ≤ n ≤ m} {0n1m | 0 ≤ m ≤ n} {0i12i | 0 ≤ i} {0i1i+1 | 0 ≤ i} {0n1m0n | n,m ≥ 0} {w ∈ {0, 1}∗ | w = wR} {wwR | w ∈ {0, 1}∗} (a) (20 points) Use (some of) the sets above, along with any regular sets you would like, to give example values for A1, A2, A3, B1, B2 such that A1 and A2 and A3 are each regular, B1 and B2 are each nonregular, and A1 ( B1 ( B2 ( A2 ( A3 Recall that X ( Y means that X is a proper subset of Y ; that is, that X ⊆ Y and that X 6= Y . For each of your examples of regular sets, clearly define the set and justify (e.g. by citing an example in the book or by proving it from scratch) why the set is regular and why the proper subset relations hold. (b) (10 points) (Graded for fair effort completeness) The Pumping Lemma is useful for proving that some sets are nonregular. Explain in two or three sentences why it is true (use your own words; do not quote the book or the videos here) and prove that a set is nonregular using the pumping lemma for an example set that is not worked out in the book or in the videos. 1 2. Consider the PDA M over the alphabet {0, 1, 2} whose state diagram is (a) (5 points) Fill in the full stack contents for each step in the following computation of M on the input string 12. Then determine whether this computation is a stuck computation, an accepting computation, or a rejecting computation. q0 q1 q1 q2 q2 q3 TOP ? TOP ? TOP ? TOP ? TOP ? TOP ? You may hand-draw and scan these traces of the computations. For full credit, include all stack contents at each step (not just the character, if any, at the top). Hint: You might find it useful to annotate the steps in the computations with which (if any) input character is consumed with each transition. Hint: To get you started, we’ve filled out a computation of M on the input string 01. There are many other computations of M on this string. q0 q1 q1 q1 TOP TOP $ TOP $ TOP X $ (b) (10 points) Describe an infinite set of strings that is a subset of L(M). For full credit, precisely define your set and refer to the state diagram to give a general description of what a successful computation of M on each strings in the set would look like. (c) (10 points) Consider the language of the context free grammar G = ({S}, {0, 1, 2}, R, S) where the set of rules R is given by S → 0S0 | 1S1 | 2 Prove that L(G) 6⊆ L(M) and that L(M) 6⊆ L(G) by giving specific counterexample strings and explaining why they prove that these subset inclusions do not hold. Hint: It might be helpful to start by describing, in set builder notation, the set L(G) using the definition of the CFG. 2 (d) (10 points) (Graded for fair effort completeness) When we introduced PDAs, we used the stack to give us access to unbounded memory in addition to the finitely many states in the state diagram. In general, for an arbitrary PDA with an arbitrary string input, is there any relationship between the length of the input string and the size of the stack during the computation of the PDA on this input? Define and justify any bounds we can state on the memory use of the PDA, or explain why there aren’t any. 3. In this question, you’ll practice working with formal general constructions for PDAs and trans- lating between state diagrams and formal definitions. Suppose M = (Q,Σ,Γ, δ, q0, F ) is a PDA. We can define a new PDA N so that L(M) = L(N) and N is guaranteed to have an empty stack at the end of any accepting computation. Informally, the construction is as follows: Add three new states q′1, q ′ 2, q ′ 3 and one new stack symbol #. • One of the new states q′1 will be the new start state and it has a spontaneous transition to the old start state q0 which pushes the new stack symbol # to the stack. • The transitions between the old states are all the same. • From each of the old accept states, add a spontaneous transition (that doesn’t modify the stack) to the second new state q′2. • In this state q′2, pop all old stack symbols from the stack without reading any input. • When the new stack symbol # is on the top of the stack, transition to the third new state q′3 and accept. Assume {q′1, q′2, q′3} ∩Q = ∅ (otherwise, relabel some of the states in Q) and assume that # /∈ Γ (otherwise, relabel this stack symbol in Γ). Define N to be N = (Q ∪ {q′1, q′2, q′3},Σ,Γ ∪ {#}, δN , q′1, {q′3}) where δN : Q∪{q′1, q′2, q′3} × Σε × Γε ∪{#} → P(Q∪{q′1, q′2, q′3} × Γε ∪{#}) is defined as δN( (q, x, y) ) = {(q0,#)} if q = q′1, x = ε, y = ε δ( (q, x, y) ) if q ∈ Q, x ∈ Σ, y ∈ Γε δ( (q, x, y) ) if q ∈ Q, x = ε, y ∈ Γ δ( (q, x, y) ) if q ∈ Q \ F , x = ε, y = ε δ( (q, x, y) ) ∪ {(q′2, ε)} if q ∈ F , x = ε, y = ε {(q′2, ε)} if q = q′2, x = ε, y ∈ Γ {(q′3, ε)} if q = q′2, x = ε, y = # ∅ otherwise (a) (10 points) Illustrate this construction by considering the PDA M from the previous ques- tions 3 and applying the construction above to create the related PDA N and include its state diagram in your submission. Note: you may include the formal definition of your PDA, but this is not required. (b) (20 points) Pick a string of length 5 over the alphabet of the PDA M and use it to demon- strate the difference in M and in N by • describing a successful computation of M on this string for which the stack is not empty at the end of the computation, and • describing a successful computation of N on this string for which the stack is empty at the end of the computation. In your descriptions of these computations, include both the sequence of states visited by the machine as well as snapshots of the full contents of the stack at each step in the computation. You may hand-draw and scan these traces of the computations. Hint: You will need to pick your example string wisely. It must be accepted by M and there must be a computation of M on your string which ends with a nonempty stack. Not all choices of length 5 strings work. (c) (10 points) (Graded for fair effort completeness) In class, we talked about how a language is recognizable by a PDA if and only if it is generated by a CFG. For an arbitrary PDA M = (Q,Σ,Γ, δ, q0, F ), let N be the PDA constructed using the general construction above. Describe how you would translate a CFG that generates L(M) to one that generates L(N). Include an informal description along with a formal description of how you would translate the formal definition for the CFG. Bonus – not for credit; do not hand in Informal descriptions of PDAs are often useful when working with complex operations. We’ve discussed several shorthands that can be used in informal descriptions such as “peek at the top of the stack, and if the character is . . . , then do . . . ”. Give another example of a useful shorthand that can be used when building PDAs, and explain briefly how you would implement it in the state diagram of a PDA. How would you translate these constructions to CFGs? Hint: For ideas of shorthands that are useful, you can look at the informal descriptions of PDAs in the book in example 2.14 (look back to page 112 for the informal version), example 2.16, and example 2.18. 4
