2.5k views

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 | 2.5k views
0

string "aaababab" generate by  regular expression

only A option accept

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

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.

by Active (4.5k points)
edited by
0
@Praveen sir, you made a DFA and question asks to select nfa from given options. Although option a is correct but didn't get your method of doing. Please explain a little bit.
0
@Swati you are right, that answer was not as correct as required.
0
@Praveen sir, Have you removed your previous answer ? I'm finding it........
0
yes, that was not correct.
0
Can not we take 'aa' as a string?
+3
R= (a+b)*(aa+bb)(a+b)* is given ..
(anything) (aa+bb) (anything)

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

ans = option a
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.
by (359 points)
0
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"