edited by
8,180 views
47 votes
47 votes

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.





edited by

4 Answers

Best answer
58 votes
58 votes

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. accepts any string containing either $\mathbf{aa}$ or $\mathbf{bb}$ and it does not accept any other string.

Option A is correct.

edited by
6 votes
6 votes
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.
2 votes
2 votes

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!

0 votes
0 votes

Since ….except option A  every FA accepting ABA

  which is not valid….

Option A is correct

Answer:

Related questions

42 votes
42 votes
7 answers
1
Ishrat Jahan asked Oct 30, 2014
7,776 views
Consider the regular expression $R = (a + b)^* (aa + bb) (a + b)^*$Which deterministic finite automaton accepts the language represented by the regular expression $R$?