1. The binary string 0011011 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 multiple of 3? b) Is the given string greater than 50? c) Is the given string a palindrome? d) Is the given string a composite number (not a prime)? 2. 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 0 Then identify one of these expressions from the list of choices below. a) 1 represents the paths from C to A that do not go through B. b) 1(0+1010)* represents the paths from C to A that do not go through B. c) 0+010 represents the paths from B to C that do not go through A. d) 0(0+10)* represents the paths from B to A that do not go through C. 3. Here are seven regular expressions: 1. (0*+10*)* 2. (0+10)* 3. (0*+10)* 4. (0*+1*)* 5. (0+1)* 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. (0*+10)* and (0*+1*)* b) (0+1)* and (0*+10)* (0+1*0)* and (0+1*)* d) (0+1)* and (0*+1*)* 4. Convert the following nondeterministic finite automaton: 1 A B 0 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) {B} ○ b) {} c) {A, B} d) {A,B,C} 5. Examine the following DFA: B 1 0 A D 0 Identify in the list below the string that this automaton accepts. ○ a) 10001 b) ε 6. What is the concatenation of abab and bab? a) abab bab b) ababbab aaabbb d) abab.bab Submit Homework c) 01111 d) 100

1. The binary string 0011011 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 multiple of 3? b) Is the given string greater than 50? c) Is the given string a palindrome? d) Is the given string a composite number (not a prime)? 2. 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 0 Then identify one of these expressions from the list of choices below. a) 1 represents the paths from C to A that do not go through B. b) 1(0+1010)* represents the paths from C to A that do not go through B. c) 0+010 represents the paths from B to C that do not go through A. d) 0(0+10)* represents the paths from B to A that do not go through C. 3. Here are seven regular expressions: 1. (0+10)* 2. (0+10)* 3. (0+10) 4. (0+1)* 5. (0+1)* 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. (0+10) and (0+1)* b) (0+1)* and (0+10) (0+10) and (0+1) d) (0+1)* and (0+1)* 4. Convert the following nondeterministic finite automaton: 1 A B 0 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) {B} ○ b) {} c) {A, B} d) {A,B,C} 5. Examine the following DFA: B 1 0 A D 0 Identify in the list below the string that this automaton accepts. ○ a) 10001 b) ε 6. What is the concatenation of abab and bab? a) abab bab b) ababbab aaabbb d) abab.bab Submit Homework c) 01111 d) 100