E*

1 (30 points) For each of the following languages, give an example of something in the language and something not in the language. Note that while the languages are tech- nically encodings of machines, just giving the state diagrams of machines is sufficient. (a) ((A) | A is a DFA and A accepts at least one string) (b) {(A) | A is an NFA and A accepts nothing} (e) (R, u) | R is a regular expression that does not generate w) (d) {(A, B1 A and B are DFAs and L(AS L(B)} (e) (M) M is a Turing machine and M loops indefinitely on all inputs) (f) {(M1, Ma) | M1 and M2 are Turing machines and L(M) = L(Ma).)