Question

If the final states and non-final states in the DFA below are interchanged, then which of the following languages over the alphabet { a, b } will be accepted by the new DFA?

• A. Set of all strings that begin with either an a or ab
• B. Set of all strings that do not end with ab
• C. Set of all strings that do not contain the substring ab.
• D. The set described by the regular expression $b^{\ast }a{a}^{\ast }(ba{)}^{\ast }{b}^{\ast }$

Answer 1

The correct option is B Set of all strings that do not end with ab

To find complement of a DFA we need to interchange final and non-final states of DFA.



Above DFA generates all strings end with ab. Complement of DFA accepts all strings do not end with ab.

Complement of given DFA is :


it accepts all strings that do not end with,