CSci 4011, Formal Languages and Automata Theory Homework 2, Fall 2020 Posted: Oct 7, 2020 Due: Oct 26, 2020 Reminder: Assignments are due by 11:59 p.m. on the due date. Please make sure to consult the...

Do the following problems in the file below.Please complete carefully and in high quality


CSci 4011, Formal Languages and Automata Theory Homework 2, Fall 2020 Posted: Oct 7, 2020 Due: Oct 26, 2020 Reminder: Assignments are due by 11:59 p.m. on the due date. Please make sure to consult the guidelines for homework submissions posted at https://z.umn.edu/csci4011submissions before you start writing up your homework. In addition, make sure to read the part of the syllabus that discusses the requirements of homework submissions to understand the factors that will impact on the grading. Remember that communicating your approach to the solution of a problem—e.g. the key ideas underlying a proof or a construction—is as important as laying out the details, and sometimes may be more important. For this reason, you should typically begin your answer to each problem with a brief discussion of these key ideas before you go into the specific details. This is not a hard-and-fast rule—sometimes the essential idea may be so apparent as to not need any further explanation—but it is a yardstick for you to consider when writing your solutions. Remember that this is a math course and in accessing math work we must look at precision as well as clarity of thought. Note that you have almost 3 weeks to do this homework. This decision has been made to allow for enough recitations in which problems on all the topics relevant to this homework can be discussed before the homework becomes due. However, you should pay attention to two important things: (a) there is more work in this homework than the previous ones, so getting started on the problems early and working through them steadily would be a good strategy for avoiding stress at the end, and (b) because there is more in this homework, it will also contribute more than the earlier homeworks to the aggregate, so you would want to do the problems really well. Problem 1 (10 points) First, let us recall notation that we have seen earlier: if x is a string, we write xR to denote the string that is the reverse of x. Provide a context-free grammar that generates the following language: {x1#x2# · · ·#xk | k ≥ 1, each xi ∈ {a, b}∗, for some i and j, xi = xRj }. To explain this language, a string belongs to the language if it consists of some number of strings over {a, b} that are separated by the letter # and some pair of the strings over {a, b} are reverses of each other. Note that i and j can be equal, so, for example, the string aba belongs to the language. 1 https://z.umn.edu/csci4011submissions Problem 2 (8 + 4 points) 1. Let Σ = {a, b}. Provide a context-free grammar that generates the language {ai bj ck | i = j or j = k}. 2. We observed (without proof) in class that any context-free grammar for the language in part (1) must be ambiguous. Exhibit this ambiguity for the grammar you have provided by showing two different parse trees for a suitably chosen string in the language. Problem 3 (10 points) Consider the grammar G given by the rules S −→ aS b | b Y | Y a Y −→ b Y | a Y | ε This is the grammar given to you in Problem 2.19 in the book. Prove that L(G) = {w ∈ {a, b}∗ | w is not of the form an bn for n ≥ 0}. Problem 4 (8 + 8 points) 1. Give an informal English description for a pushdown automaton that will accept the following language: {w ∈ {a, b}∗ | w has twice as many bs as as}. 2. Translate the informal English description into an actual pushdown automaton. In presenting this automaton, use a state diagram like that in Figure 2.15 in the textbook. In other words, do not try to write down a mathematical description in the form of a 6-tuple, this could be quite tedious and unnecessary for communication between humans. However, make sure to follow the informal English description you have provide in the first part of this problem; how faithfully you have followed that description will be a criterion in grading. Problem 5 (8 points) Do Exercise 2.14 from the book. Problem 6 (6 + 6 points) Suppose that L is a context-free language and that R is a regular language. Show then that 1. L − R must be context free. Note that “minus” between sets represents set difference, i.e. L−R is the set of all strings in L that are not in R. In doing this part, assume the result in Problem 2.18 part (a) in the textbook. 2 2. R − L may not be context-free. When I did this part, I found use for the observation that context-free languages are not closed under complementation, something that you will see in one of the discussion problems for Week 7; you may use this observation in anticipation of that result. Problem 7 (8 + 8 + 8 points) Use the pumping lemma to show that the following languages are not context free: 1. {ai bj ck | i ≤ j and k ≤ j}; the alphabet, Σ, here is {a, b, c}. 2. The language described in Problem 2.30, part (d), in the book. You would want to compare this language with that in Problem 1 above and understand the difference. 3. {w tw | w, t ∈ {0, 1}+}. Problem 8 (10 points) Given two languages A and B, let A/B denote the language {w | w x ∈ A for some x ∈ B}. Show that if A is a context-free language and B is a regular language, then A/B is a context-free language. Hint: Think of constructing a PDA for A/B from a PDA for A and a DFA for B. After initially behaving like the PDA for A, this PDA will have to make transitions as both the PDA for A and the DFA for B would, but it would do this on a phantom or imagined input. If you follow this suggestion, you should define the new PDA precisely based on the PDA for A and the DFA for B and you should explain how that PDA implements this intuition. 3