Complete 4 problems in the file below
CSci 4011, Formal Languages and Automata Theory First Mid-Term Exam, Fall 2020 Note: You must submit your solutions via Gradescope in the format indicated before noon on Oct 14, 2020. This deadline is sharp; late submissions will get no credit. Please read the rest of this preamble before you start the exam. You will be responsible for doing so: your not having read it will not mitigate the impact of violating any of the protocols described below. Your taking the exam implies that you have knowledge of the honesty requirements which have also been made explicit in other ways before this point. The overarching requirement is that your answers must be based solely on your own understanding of the material the exam covers prior to your viewing the questions. More specifically, 1. The exam must be done without consulting any source other than the textbook. Before you look at the exam, you must put aside all other books, notes, etc, and not view these again till you have turned in your answers. 2. You must not consult any web sources for help with the exam or discuss the problems with anyone, regardless of whether it is someone taking the course with you or not, between the time when you first look at the questions and when you turn in your solutions. Violations of these rules or the general principle they explicate will be adequate grounds for the award of a failing grade in the course. The exam has four problems, all of which must be answered for full credit. Each problem is annotated with the points associated with it and the points for all the problems total up to 100. You should submit your answers to these problems in the form of a PDF file that can be a clean scan of legible handwritten solutions. Begin the answer to each question on a separate sheet. Submissions must use Gradescope and they should follow the protocol described for homeworks that you will find at the following URL: https://z.umn.edu/csci4011submissions An exception to what you find on the page above: you do not need to begin subparts of a question on different pages, this kind of separation only at the level of problems will suffice. Note that it is as important to make clear how you have solved a problem as it is to present the details of a solution. For problems involving the application of a method discussed in the book or in lectures, you should show your work and also follow the method closely. For problems involving a proof based on a construction, it is never adequate to simply present the construction: you should explain the idea underlying the construction, make it clear why the idea is correct and only then play out the details of the construction. In general, in mathematical work, it is not sufficient to simply provide details, it is perhaps even more important to explain why the details “work.” Note also that proceeding in this way provides us a means for giving you partial credit for problems that you have not been able to solve completely or when you get specific details wrong. Good luck! 1 https://z.umn.edu/csci4011submissions Problem I. (12 + 0 + 18 points) 1. Assume that the alphabet is {a, b}. Use the idea in the proof of Lemma 1.55 to construct an NFA that accepts the language given by the regular expression (aa ∪ ba)∗bab. You do not have to present each step in the process, it only needs to be apparent from the NFA you present that you have used the construction the proof yields. 2. Simplify the NFA you have provided in the first part by removing epsilon transitions that can obviously be removed, also eliminating states in the process. The correctness of your simplifications should either be obvious or should be briefly explained. 3. Convert the NFA you have the end of part 2 to a DFA using the method discussed in class. You must show your work for credit in this part. While there is no credit for part 2, actually doing it will reduce the tedium in part 3. However, be careful about your simplifications: if they are incorrect, this will impact on the credit for part 3. Problem II. (18 points) Let u and v be two particular strings over an alphabet Σ. Prove that the following language B = {w ∈ Σ∗ | w contains u as a substring but does not contain v as a substring} is regular. As a hint, think of using operations under which regular languages are known to be closed to simplify your argument. Problem III. (22 points) Using the pumping lemma, prove that the language {1n | n is a prime number} is not regular. Problem IV. ((5 + 5) + 20 points) Let swap every two be an operation on languages that is defined as follows: swap every two(L) = {a2a1a4a3 . . . a2na2n−1 | a1a2a3a4 . . . a2n−1a2n ∈ L where a1, . . . , a2n ∈ Σ} In this definition, Σ is the alphabet for the language L. 1. What languages result from applying swap every two to the following languages: (a) {1n | n ≥ 0}, where the alphabet is {1}. (b) {(01)n | n ≥ 0}, where the alphabet is {0, 1}. 2. Show that if L is a regular language then so it swap every two(L). Hint: Try to construct an automaton accepting swap every two(L) from a DFA accepting L. The automaton you construct should conceptually process the input symbols in pairs, using its finite control to somehow remember the first symbol of the pair. If you use such a “proof-by-construction” approach, you should define the automaton formally and provide a brief, informal argument to show that your automaton accepts swap every two(L). 2