dfd

1 Equivalent DFA and NFA Two machines are equivalent if they accept the same strings (i.e., if they recognize the same language). Come up with an NFA that is equivalent to the DFA from the DFA Formal Description problem in Homework 1. Your answer must be a formal description of an NFA. (You may want to check that your string examples are appropriately accepted or rejected by this NFA.) 1 DFA Formal Description Imagine you have been given the task of checking whether a given password contains a "special character". The following FSM (DFA) represents computation that could do this. More specifically, it accepts all strings containing at least one $ character. 1. Come up with 2 strings that are accepted by the DFA. These strings are said to be in the innguage recognized by the DFA. 2. Come up with 2 strings that are not accepted (rejected) by the DFA. These strings are not in the language recognized by the DFA. 3. Is the empty string, , in the language of the DFA? 4. Come up with a formal description for this DFA. Recall that a DFA's formal description is a tuple of five components, e.g. 1. Come up with 2 strings that are accepted by the DFA. These strings are said to be in the language recognized by the DFA. 2. Come up with 2 strings that are not accepted (rejected) by the DFA. These strings are not in the language recognized by the DFA. 3. Is the empty string, , in the language of the DFA? 4. Come up with a formal description for this DFA Recall that a DFA's formal description is a tuple of five components, e.g. M=(Q,,,qtatart,F). You may assume that the alphabet contains only the symbols from the diagram. 5. Then for each of the following, say whether the computation represents an accepting computation or not (make sure to review the definition of an accepting computation). If the answer is no, explain why not.: a. (q0,abb) b. (q1,ab) ci (q0,abc) d. (q0,eds)