geeks for geeks

Question

Which regular expression best describes the language accepted by the non-deterministic automaton below?

 
(A) (a + b)* a(a + b)b
(B) (abb)*
(C) (a + b)* a(a + b)* b(a + b)*
(D) (a + b)*


Answer: (A) 

DOUBT-  above given DFA can accept string (aaab) but the expression in option A can not accept aab. therefore, A is wrong answer, then what is correct answer?

Comments

In question they give NFA not DFA . And (a + b)* a(a + b)b include aab also check again 

From (a + b)* take Null

a take a since no choice

(a + b) take a since we have choice either take a or b 

b take b here since no choice.

---

Option A can accept string aab

(a + b)* a (a + b)b 

Since (a + b)* is *, so you have option to choose nothing, so choose nothing

from the rest     a (a + b)b 

take                                   a

and from (a  + b), choose     a

and from last take                b

Answer 1

To approach such answers we have to always find smallest possible string accepted by language

it is aab or abb

Now we have to see state characteristic

so at initial state a string starting with b will remain in initial state if string starts with a then it has two options either go ahead or remain in same state

so (a+b)^* a ..1

second state either a comes or b comes it advances to next state

so (a+b)  ...1

at third state string should have b else it will be in dead end so

b  ...1

once reached final state nothing should be accepted or string should terminate

so we but this up we have (a+b)^*a(a+b)b

it contains both smallest possible string aab as well as abb

Another approach is eliminating options

in option B smallest possible string is $\epsilon$ which is not accepted so false

in option C smallest possible string is b which is also not accepted so false

in option D smallest possible string is $\epsilon$ which is not accepted so false

First of all its NFA so it has choice at initial step both aaab and aab is generated by option A and accepted by NFA also