Exam 1
DUE: February 24 at 10:45am on CourseSite
CSE 318: Spring 2020
Important: This exam is take home. You may use your notes and homework, my completed notes and homework solutions posted on CourseSite, and our class text book. However, you may not consult other text books, resources (on- and offline), or other people. This includes outside solutions (full and in part) made available by professors or students, both at Lehigh or other institutions. You may not collaborate with other people, both in the class and outside of class. Exams will be carefully checked for any evidence of plagiarism, and any academic integrity violations will be immediately reported.
By submitting your work, you are affirming that you have neither given nor received any unauthorized aid on this exam.
This exam is out of 150 points, and your grade will be based on the full 150 points. There are 7 questions, and you must complete all 7 questions. While you are not required to, please submit any JFLAP files you use. This will allow me to check your work carefully by running simulations (in the event that your answer differs drastically from mine, or I cannot follow your logic given just the state diagram.). Show all work to allow for possible partial credit.
SUBMISSIONS: You must submit your written (or typed) solutions as a single pdf, and any JFLAP files must be compressed into a single zip file. Please name any JFLAP files you submit (not the zip file, the files within it) descriptively enough that I know which problems they correspond to. Late submissions will not be accepted.
Please write all solutions on separate sheets of paper and clearly indicate which questions you are answering.
1
1. (25 points) Let M be the DFA below.
(a) Provide a formal definition of M using the 5-tuple described in class. Make sure to provide the definition of each element of this 5-tuple.
(b) In English, describe the language recognized by this DFA.
(c) Using your answer from part (b), construct a regular expression that describes the language recognized by this DFA.
(d) Is this language regular? Carefully explain your answer.
2. (25 points) Answer each of the following. You should use each part to help you answer subsequent parts.
(a) Build an NFA M1 that accepts (a ∪ b)∗.
(b) Build an NFA M2 that accepts b(a ∪ b)(a ∪ b)
(c) Using M1 and M2, build an NFA M that accepts (a ∪ b)∗b(a ∪ b)(a ∪ b)
(d) Given the NFA you built in part (c), what is the maximum number of states the equivalent DFA
could have? Be sure to justify your answer.
(e) Determine the validity of the following statement: If A is a regular language and B is a finite
language, then A ◦ B is also a regular language. Briefly justify your answer.
3. (20 points) Decide whether the following statements are true or false. Provide a brief explanation for full credit. For statements you indicate to be false, counterexamples suffice as “explanation”. Explanations for “true” statements must be slightly more rigorous (though, full proofs are not required).
(a) If L2 is a nonregular language and L1 ⊂ L2, then L1 is also nonregular.
(b) If L1 is nonregular and L2 is nonregular, then L1 ∪ L2 must be nonregular.
(c) Let L1 and L2 be regular languages, then L1 ∩ L2 is also a regular language. (d) If L is a nonregular language, then L∗ must also be nonregular.
4. (15 points) The set {bawab|w ∈ {a, b}∗} is regular over {a, b}. Using the bases {a} and {b}, and using the recursive definition given in class for regular expressions, show how a finite number of applications of the operations concatenation, union, and Kleene star can generate this language. Your final answer should also include the regular expression that describes this language.
2
5. (25 points) Consider the following NFA M
(a) Construct the transition table of M. Make sure to include all nodes and their outputs when constructing this table.
(b) Convert this transition table to one for M′, the equivalent DFA that recognizes L(M). Make sure to include all nodes and their outputs when constructing this table.
(c) Draw the DFA corresponding to the transition table you constructed in part (b).
(d) Trace two computations of the string aab in M, and determine whether aab ∈ L(M).
6. (20 points) Consider how to we convert finite automata to regular expressions and vice versa.
(a) Let M be the NFA
Give a regular expression for L(M).
(b) (20 points) Convert the following regular expression into a finite automaton that recognizes the
same language.
7. (20 points) Answer all questions below.
(b+a)∗(a ∪ b)(ba)∗
(a) In your own words, explain how the pumping lemma gives us regularity of a language.
(b) Again in your own words, explain why it is impractical to use the pumping lemma to prove a language is regular, yet useful to prove a language is not regular.
(c) Use the pumping lemma to prove that A = {an bm |n < m} is nonregular. Assume Σ = {a, b}. 3