Name
________________________________________________ Student No
___________ No 1. Given the alphabet V = {0, 1}. (a) Give the first 16 elements of V*V in lexicographic order. (b) How many elements does V*V have? No 2. Let A and B be arbitrary
languages on an alphabet V. Prove the following true by showing set
containment in both directions or prove false by giving a
counterexample: No 3. Give the state diagram of a DFA over the alphabet V = {0, 1} that accepts a string if the substring 101 appears. No 4. Give the state diagram of a NFA without ε-transitions, over the alphabet V = {0, 1), that accepts strings of one or more occurrences of 01, or one or more occurrences of 10. N o 5. Use the subset algorithm to find a DFA that accepts the same strings as the following NFA A, 1 -> B A, 1 -> C B, 0 -> B B, 1 -> C C, 1 - > B No 6. (a) Give the state diagram of a NFA, without ε-transitions, that recognizes the regular expression (0 U 1)*1011(0 U 1)*. That is, it accepts strings that contain 1011 as a substring. (b) Give the state diagram of a DFA that recognizes the same language as this NFA. No 7. Prove that the language L over the alphabet V = {0, 1} consisting of strings with an even number of 1’s is regular. No 8. Write the system of end set equations for the NFA in No 5. Use Arden’s Rule to solve this system to obtain the regular expression recognized by the NFA. No 9. (a) Give the state diagram for the ternary accepter, that is the DFA accepts strings over the alphabet V = {0, 1} in which the number of 1’s is a multiple of three. (b) Write the system of end set equations for this DFA. (c) Use Arden’s Rule to obtain the regular expression recognized by this DFA. No 10. Use the Pumping Lemma to prove that the language L = { 0(k+1)1k | k > 0 } is not regular. |
|
|
CE160 First Exam - Practice |