GATE IT 2008 | Question: 32

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 do not end with $ab$
• B. Set of all strings that begin with either an $a$ or $a \ b$
• C. Set of all strings that do not contain the substring $ab$,
• D. The set described by the regular expression $b^*aa^*(ba)^*b^*$

Comments

@Abhrajyoti00 in (a+b)*(a+bb) epsilon will not be generated as epsilon also not end with ab.

---

@Abhrajyoti00 your Regex wont accept $e, b$ but it should accept it.

---

What is the regular expression for the new DFA ?

Answer 1

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$. 

Comments

 @Praveen Saini option b says begin with ab not b!

---

begin with either an a or a b.

---

$DFA$ given in question produces all strings ending with $ab$ 

Regex -  $(a+b)^*ab$.

Answer 2

A option

Comments

i think d

---

Option d also accepts string 'a' but the automata in the figure does not.

---

ohh yes..:)

Answer 3

L={ENDS WITH ab };

L"={ DOES NOT ENDS WITH ab };

THAT MEANS OPTION (A)

Answer 4

 

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*.