see the file
D:/Ostfalia/UWP/UWP-2020/CompModels/Exams/Exam1CSCI431.dvi University of Wisconsin – Parkside March 31, 2020 Department of Computer Science 3:30pm - 4:52pm Prof. Dr. F. Seutter Computational Models (CSCI 431), Spring 2020 Examination, Midterm 1. Give state diagrams of DFAs recognizing the following languages. The alpha- bet is {0, 1}. (a) {w | w is any string except 11 and 111} (b) {w | every odd position of w is a 1} (3+3 points) 2. Use the subset construction to convert the NFA N = ({1, 2}, {a, b}, δ, 1, {1}) to an equivalent DFA M . δ is defined as follows: δ: a b ǫ 1 {1, 2} {2} ∅ 2 ∅ {1} ∅ Give the state diagram of M . (6 points) 3. Give regular expressions generating the following languages. The alphabet is {0, 1}. (a) {w | w contains the substring 11 at least once} (b) {w | w contains the substring 11 exactly once} (c) {w | w contains the substring 11 at most once} (2+2+2 points) 4. (a) Give a context-free grammar G that generates the language A = {1i0j1k | i = j or j = k where i, j, k ≥ 0}. (b) Is your grammar G ambiguous? Why or why not? (4+2 points) 1 5. Let M be a DFA that recognizes language A over alphabet Σ. Swapping the accept and non-accept states in M then yields a DFA M ′ that recognizes the complement of A, i. e. L(M ′) = L(M) = A = Σ∗ \A. (a) Show by giving an example that, if N is an NFA that recognizes language B, swapping the accept and nonaccept states in N doesn’t necessarily yield an NFA N ′ that recognizes the complement of B, i. e. L(N ′) 6= L(N) = B = Σ∗ \B. i. Give a language B over alphabet {0, 1}. ii. Give an NFA N (state diagram) where L(N) = B with four states or less. iii. Give the NFA N ′ (state diagram). iv. Give a string s ∈ L(N ′) but s /∈ B. (b) Is the class of languages recognized by NFAs closed under complement? Explain your answer. (4+2 points) 2 D:/Ostfalia/UWP/UWP-2020/CompModels/Exams/Exam1CSCI431.dvi University of Wisconsin – Parkside March 31, 2020 Department of Computer Science 3:30pm - 4:52pm Prof. Dr. F. Seutter Computational Models (CSCI 431), Spring 2020 Examination, Midterm 1. Give state diagrams of DFAs recognizing the following languages. The alpha- bet is {0, 1}. (a) {w | w is any string except 11 and 111} (b) {w | every odd position of w is a 1} (3+3 points) 2. Use the subset construction to convert the NFA N = ({1, 2}, {a, b}, δ, 1, {1}) to an equivalent DFA M . δ is defined as follows: δ: a b ǫ 1 {1, 2} {2} ∅ 2 ∅ {1} ∅ Give the state diagram of M . (6 points) 3. Give regular expressions generating the following languages. The alphabet is {0, 1}. (a) {w | w contains the substring 11 at least once} (b) {w | w contains the substring 11 exactly once} (c) {w | w contains the substring 11 at most once} (2+2+2 points) 4. (a) Give a context-free grammar G that generates the language A = {1i0j1k | i = j or j = k where i, j, k ≥ 0}. (b) Is your grammar G ambiguous? Why or why not? (4+2 points) 1 5. Let M be a DFA that recognizes language A over alphabet Σ. Swapping the accept and non-accept states in M then yields a DFA M ′ that recognizes the complement of A, i. e. L(M ′) = L(M) = A = Σ∗ \A. (a) Show by giving an example that, if N is an NFA that recognizes language B, swapping the accept and nonaccept states in N doesn’t necessarily yield an NFA N ′ that recognizes the complement of B, i. e. L(N ′) 6= L(N) = B = Σ∗ \B. i. Give a language B over alphabet {0, 1}. ii. Give an NFA N (state diagram) where L(N) = B with four states or less. iii. Give the NFA N ′ (state diagram). iv. Give a string s ∈ L(N ′) but s /∈ B. (b) Is the class of languages recognized by NFAs closed under complement? Explain your answer. (4+2 points) 2