GATE IT 2007 | Question: 71

Question

Consider the regular expression $R = (a + b)^* (aa + bb) (a + b)^*$

Which of the following non-deterministic finite automata recognizes the language defined by the regular expression $R$? Edges labeled $\lambda $ denote transitions on the empty string.

• A.
  
• B.
  
• C.
  
• D.
  

Comments

string "aaababab" generate by  regular expression 

only A option accept 

and abab not generate by re but option c,d,e accepted

---

@mohan I think "aaababab" will be accepted by figure B.

a : S0->S1

a: S1-> S2

a b a b a : Self loop on S2

b : S2 -> S3 (final state)

Please do correct me if I'm wrong.

Answer 1

When we say non-deterministic finite automata recognizes the language defined by the regular expression $R$ then it means that  it won't accept any other string that does not fall under the $R$ and it will only accept all strings that fall under $R$. $R$ says the string should contain either $\mathbf{aa}$ or $\mathbf{bb}.$

So, we see B accepts $\mathbf{aba}$, C accepts $\mathbf{aba}$ and D accepts $\mathbf{a}.$ Just find some examples that do not follow the rule. A accepts any string containing either $\mathbf{aa}$ or $\mathbf{bb}$ and it does not accept any other string.

Option A is correct.

Comments

Can not we take 'aa' as a string?

---

R= (a+b)*(aa+bb)(a+b)* is given ..
 (anything) (aa+bb) (anything)

option a- (anything) (aa+bb) (anything)

option b- start with either a or b.

option c- start with either a or b

option d- start with either a or b

ans = option a

---

No ankit .. see a starts with a but not accepted by B and C option so

option b- start with either a or b.
option c- start with either a or b

is wrong .

similarly b is not accepted by option D so saying start with either  b is incorrect .

Answer 2

Even by seeing at first, due to (a+b)* at the beginning and end of the string, there have to have loops, which are only present in OPTION A as THIS IS AN NFA.

Now, when we see first a or first b, we continue with (aa+bb) part of the string, we continue with the string. If after first a or first b, a 'b' or an 'a' occurs, we redirect it to the opposite branch and club the first 'a' or first 'b' with the (a+b)* part of the string. Else, everything goes as planned.

Comments

yes as nfa's main purpose is to show what is being accepted and show them only in the automata, excluding the other inappropriate transitions, and by option we can easily figure out that (A) suits best to its definition i.e "anything (aa+bb) anything"

Answer 3

Simply take the string '​​​"aba" and check!

You will find option b, c, and d invalid.

Further you can check option in more detail using any string that is accepted by language, as well those strings that should be rejected by the language. 

Option A IS the correct answer!

Answer 4

Since ….except option A  every FA accepting ABA

  which is not valid….

Option A is correct