edited by
8,818 views
35 votes
35 votes

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?

  1. Set of all strings that do not end with $ab$
  2. Set of all strings that begin with either an $a$ or $a \ b$
  3. Set of all strings that do not contain the substring $ab$,
  4. The set described by the regular expression $b^*aa^*(ba)^*b^*$
edited by

4 Answers

Best answer
45 votes
45 votes

Above DFA is for regular expression $(a+b)^*ab$. All strings end with $ab$. 

Complement of DFA accepts all strings does not end with $ab$. 

DFA(L') is:

B. String begin with either $a$ or $b$.

$ab$ (string start with $a$) doesn't accept in it reach to nonfinal state $q_2$.

$bab$ (string start with $b$) doesn't accept in it reach to nonfinal state $q_2$.

C. Set of strings that do not contain the substring $ab$ 

$aba$ (have substring $ab$) does accept in it reach to final state $q1$.

D. The set described by the regular expression $b^*aa^*(ba)^*b^*$

$b$ is string accepted by DFA(L') but above regular expression cannot derive it.

Option A is correct.

DFA (L') accepts all strings that doesn't end with $ab$. 

edited by
1 votes
1 votes
A option
1 votes
1 votes

 


Option B: abab is not accepted by given RE.
Option C: aba is accepted by given RE.
Option D: ab is not accepetd by RE and it belongs to b*aa*(ba)*b*.

Answer:

Related questions

56 votes
56 votes
6 answers
1
Ishrat Jahan asked Oct 28, 2014
12,429 views
Consider the following two finite automata. $M_1$ accepts $L_1$ and $M_2$ accepts $L_2$.$M_1$$M_2$ Which one of the following is TRUE?$L_1 = L_2$$L_1 \subset L_2$$L_1 \ca...
30 votes
30 votes
5 answers
2
Ishrat Jahan asked Oct 27, 2014
10,705 views
Let $N$ be an NFA with $n$ states and let $M$ be the minimized DFA with m states recogniz­ing the same language. Which of the following in NECESSARILY true?$m \leq 2^n$$...
44 votes
44 votes
7 answers
4
Ishrat Jahan asked Oct 28, 2014
14,823 views
Consider a CFG with the following productions.$S \to AA \mid B$$A \to 0A \mid A0 \mid 1$$B \to 0B00 \mid 1$$S$ is the start symbol, $A$ and $B$ are non-terminals and 0 an...