1. Suppose A-[a), B-(b], C (1,2. Give the transition diagram for a nondeterministic finite state machine with alphabet E -fa,b,1,2] that accepts the strings x that are elements of the set A*B C*B A*. So for example, your machine should accept the string aaabb1221ba and the string bbb2ba and the string abbba but should not accept the string ab or the string 12ba or the string aaa111ba. Be sure to indicate the start and accept states. 2. Give the transition diagram for a nondeterministic finite state machine, with-a,b,c), that accepts the set of x E " such that x contains at least one occurrence o f the string ca immediately preceded by an even number of b's (at least 2) followed by an odd number of b's. So for example, your machine should accept the string bbbbcabbbbb and the string bbcacabbbbcabbbccc and the string cabbcabbbca but it should not accept the string ca or the string ccabc or the string bbcacabbb. Be sure to indicate the start and accept states 3. Consider the following nondeterministic finite state machine: N=((q0,al,q2,q3},{a,b,c},A,q0,(q2,q3)) 0 a.c a,c b.c (a) Is the string cca accepted by N? (b) Is the string acccaa accepted by N? (c) Is the string baccac accepted by N? (d) Construct an equivalent deterministic finite state machine using the subset construction. Give a transition table specifying the transition function. Omit inaccessible states (e) Name one inaccessible state that you omitted from your transition table