DFSM Deterministic Finite State Machine NDFSM Nondeterministic Finite State Machine ISI The count of elements in a set S: l|-0; K , abc)| Iwl The count of symbols in string w: lE1 0; labcl 3 2 Each T/F question is worth two points. T F 2. = {a), S = { L : L is a language over }. Isl = T F 3. R (1,2), (2,3) . The reflexive and transitive closure of R is: L(M), as long as F 4. An NDFSM M that decides a language L could accept a string w it accepts at least one other string w2 e L F 5, # {a,b), and L is a language over . L u L r. T F 6. L = { w: w = ann, n 2m, m 20, I is oddy, a is the second string in a T F 7. -(a,b), L (w : w e anbn, n2 0). The number of indistinguishability T F 8, = {a, b), M is a DFSM, and L(M) = { w : is odd }. The start state of TF 9. Every state in a DFSM that is not an accept state is a dead state. T F 10. The future behavior of a DFSM is a function only of its current state and the T F 11. There are languages that can be recognized by an NDFSM that cannot be T F 12. A configuration of a DFSM M is an element of K , where K is the set of T F 13, = {a,b), L = { s : s ends with a }. lexicographic ordering of L equivalence classes in L is finite. an accept state. input left to be read. recognized by a DFSM. states in M, and 2 is the alphabet of L(M). w e L iff it matches the regular expression: (a b')'a w e L iff it matches the regular expression: (bab)* T F 14. (a,b, L w: every a in w is immediately preceded and followed by b)