1. Examine the following DFA: B 0 1 A D 1 Ο 0 Identify in the list below the string that this automaton accepts. a) ε b) 0110 c) 0111010 d) 10000 2. The binary string 1000000 is a member of which of the following problems? Remember, a "problem" is a language whose strings represent the cases of a problem that have the answer "yes." In this question, you should assume that all languages are sets of binary strings interpreted as base-2 integers. The exception is the problem of finding palindromes, which are strings that are identical when reversed, like 0110110, regardless of their numerical value. a) Is the given string not a perfect square? b) Is the given string less than or equal to 50? Is the given string not a multiple of 3? d) Is the given string a prime? 3. What is the concatenation of abc and cda? a) abccda b) abc||cda c) cdaabc d) acbdca 4. Convert the following nondeterministic finite automaton: 1 A B C 1 to a DFA, including the dead state, if necessary. Which of the following sets of NFA states is not a state of the DFA that is accessible from the start state of the DFA? a) {A} b) {A,C} 5. Here are seven regular expressions: 1. (0*+10*)* 2. (0+10)* 3. (0*+10)* 4. (0*+1*)* 5. (0+1)* c) {A, B} d) {C} 6. (0+1*0)* 7. (0+1*)* Determine the language of each of these expressions. Then, find in the list below a pair of equivalent expressions. a) (0+1)* and (0*+10)* b) (0+10)* and (0*+10)* c) (0+10)* and (0*+1*)* d) (0*+10*)* and (0+10)* 6. When we convert an automaton to a regular expression, we need to build expressions for the labels along paths from one state to another state that do not go through certain other states. Below is a nondeterministic finite automaton with three states. For each of the six orders of the three states, find regular expressions that give the set of labels along all paths from the first state to the second state that never go through the third state. A 1 B C 1 Then identify one of these expressions from the list of choices below. a) 0(0+10)* represents the paths from B to A that do not go through C. b) 1 represents the paths from C to B that do not go through A. c) ((1+11)0)*1 represents the paths from C to B that do not go through A. ○ d) 1+101 represents the paths from C to B that do not go through A. Submit Homework

1. Examine the following DFA: B 0 1 A D 1 Ο 0 Identify in the list below the string that this automaton accepts. a) ε b) 0110 c) 0111010 d) 10000 2. The binary string 1000000 is a member of which of the following problems? Remember, a "problem" is a language whose strings represent the cases of a problem that have the answer "yes." In this question, you should assume that all languages are sets of binary strings interpreted as base-2 integers. The exception is the problem of finding palindromes, which are strings that are identical when reversed, like 0110110, regardless of their numerical value. a) Is the given string not a perfect square? b) Is the given string less than or equal to 50? Is the given string not a multiple of 3? d) Is the given string a prime? 3. What is the concatenation of abc and cda? a) abccda b) abc||cda c) cdaabc d) acbdca 4. Convert the following nondeterministic finite automaton: 1 A B C 1 to a DFA, including the dead state, if necessary. Which of the following sets of NFA states is not a state of the DFA that is accessible from the start state of the DFA? a) {A} b) {A,C} 5. Here are seven regular expressions: 1. (0+10)* 2. (0+10)* 3. (0+10) 4. (0+1)* 5. (0+1)* c) {A, B} d) {C} 6. (0+10) 7. (0+1) Determine the language of each of these expressions. Then, find in the list below a pair of equivalent expressions. a) (0+1)* and (0+10) b) (0+10)* and (0+10) c) (0+10)* and (0+1)* d) (0+10)* and (0+10)* 6. When we convert an automaton to a regular expression, we need to build expressions for the labels along paths from one state to another state that do not go through certain other states. Below is a nondeterministic finite automaton with three states. For each of the six orders of the three states, find regular expressions that give the set of labels along all paths from the first state to the second state that never go through the third state. A 1 B C 1 Then identify one of these expressions from the list of choices below. a) 0(0+10)* represents the paths from B to A that do not go through C. b) 1 represents the paths from C to B that do not go through A. c) ((1+11)0)*1 represents the paths from C to B that do not go through A. ○ d) 1+101 represents the paths from C to B that do not go through A. Submit Homework