1. (Membership problem for a DFA). Input: A (deterministic) finite automaton is a 5-tuple M (Q, 3, go, A, 5), where Q is a finite set of states, is a finite input alphabet, qo e Qis the initial state, AgQ is the set of accepting states, an Q x Q is the transition function. Note: From state q the machine will move to state o(q, G) if it receives input symbol o. In other words, the destination state is unique hence FA is deterministic (DFA). Example Graph of a DFA Accepts all strings without two consecutive 1's. 0,1 Start Previous Consecutive Previous string OK, string ok, 1's have does not ends in a been seen. end in 1 single 1