The Gateway to Computer Science Excellence
+30 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.

in Theory of Computation by Boss (16.3k points)
edited by | 2.5k views

string "aaababab" generate by  regular expression 

only A option accept 

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

2 Answers

+28 votes
Best answer

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
@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.
@Swati you are right, that answer was not as correct as required.
@Praveen sir, Have you removed your previous answer ? I'm finding it........
yes, that was not correct.
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
+5 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.
by (359 points)
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"

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,587 answers
101,840 users