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

[aa*(ba)*b* + b]* + (a+ba)* is this the regular expression for the complement of the language?

---

regular expression (L) : (b+a(a+ba)*bb)*a(a+ba)*b

regular expression (~L):  (   (b+a(a+ba)*bb)  +  (b+a(a+ba)*bb)*a(a+ba)* ) *

is this correct regexp of  L and ~L ???

---

https://youtu.be/nagYqfzY2HE?t=375

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

Answer 5

Complementing DFA gives the complement of a language shown by a DFA. So directly complementing a DFA gives the complement of the language.

Whereas complementing NFA does not mean we get the language complement as NFA moves are not deterministic a single move can be defined for more than 1 state. So for NFA complementation first understood the language shown by it and then complement the language or convert it to DFA and then say the complement directly.

 

Here the state automata is given as DFA which means complementing it would directly give the complement of the language.

So the given DFA accepts every string that ends with ab. Complement is every string acceptance that do not end with ab.