GATE2007-IT-71

3.2k 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
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.

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

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!

Related questions

1
2.6k 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$?
Consider the following finite automata $P$ and $Q$ over the alphabet $\{a, b, c\}$. The start states are indicated by a double arrow and final states are indicated by a double circle. Let the languages recognized by them be denoted by $L(P)$ and $L(Q)$ respectively. The automation which recognizes the language $L(P) \cap L(Q)$ is :
Consider the following DFA in which $S_0$ is the start state and $S_1$, $S_3$ are the final states. What language does this DFA recognize? All strings of $x$ and $y$ All strings of $x$ and $y$ which have either even number of $x$ and even number of $y$ or odd number of $x$ ... strings of $x$ and $y$ with either even number of $x$ and odd number of $y$ or odd number of $x$ and even number of $y$
Consider the regular expression $R = (a + b)^* \ (aa + bb) \ (a + b)^*$ Which one of the regular expressions given below defines the same language as defined by the regular expression $R$ ? $(a(ba)^* + b(ab)^*)(a + b)^+$ $(a(ba)^* + b(ab)^*)^*(a + b)^*$ $(a(ba)^* (a + bb) + b(ab)^*(b + aa))(a + b)^*$ $(a(ba)^* (a + bb) + b(ab)^*(b + aa))(a + b)^+$