Question

Any answer that involves a design for a Finite Automaton (DFA or NFA) should contain information about the following five components of the FA (corresponding to the 5-tuple description):

i) The set of states Q; ii) the alphabet Σ; iii) the start state; iv) the set of final states F; v) the set of transitions δ, which can be either shown in the form of a state diagram (preferred) or a transition table. You can either present the answer in the form of a state diagram with all the above information (as shown in the left side of slide #8 in the Finite Automata lecture notes) or in the tabulated form (as shown in the right side of the same slide). State diagram representation is preferred.

1. Give a DFA for each of the following languages defined over the alphabet Σ = {0, 1}:

a) (3 points) L={ w | w contains the substring 010 }

b) (3 points) L={ w | w ends in 001 }

c) (4 points) L={ w | w has a 0 in its 2 nd last position, if such a position exists}

Answer 1