2.1k views

Consider the machine $M$:

The language recognized by $M$ is:

1. $\left\{ w \in \{a, b\}^* \text{ | every a in$w$is followed by exactly two$b$’s} \right\}$

2. $\left\{w \in \{a, b\}^* \text{ | every a in$w$is followed by at least two$b$’s} \right\}$

3. $\left\{w \in \{a, b\}^* \text{ |$w$contains the substring ‘$abb$’} \right\}$

4. $\left\{w \in \{a, b\}^* \text{ |$w$does not contain ‘$aa$’ as a substring} \right\}$

edited | 2.1k views
+1
I found b,c,d as correct. which is the most appropriate?
+7
if option C. is correct then string "abbaa" should be accepted but it's not.

if option B is correct then string "b*" should be accepted.

if option D is correct then string "a" should be accepted.
+12
@Vikrant: b is the answer assuming start start state is also accepting rt? I guess it was a printing mistake.
0
It should be aa not just a
+1

Key point-> For the string which is like contain there is no Dead state only final state will be there.

so C is wrong.

A is Wrong, since $abbb$ is accepted. ($1$ a is followed by more than $2$ $b$'s)

C is Wrong, since $abba$ contains $abb$ as substring, but is still not accepted.

D is Wrong, since $ab$ does not contain $aa$ as substring, but is still not accepted.

edited
+22

option B.

Every a is followed by atleast two b's

if there is no a , then anything of b and ^ should be accept

and if there is a then it must be followed by atleast 2 b's

here regular expression = b*abb(b+abb)*

so it is sure every a is followed by atleast 2 b's and sting contain atleast one a .

0
i think answer should be b,c,d bcz in c option,there is no such string exist which is not accepted by dfa with substring abb..same reason for d also(i think something mistake in figure)
0
nice catch praveen sir
0
How option (B) is correct. Let us assume b is a string. Here that string also belong to that language but it is not accepted by this given dfa.
Most of us might be having confused between option (B) and (D).

Lets look at option (D) :

{w∈{a,b}∗ | w does not contain ‘aa’ as a substring}

which means that any Language L that does not contain 'aa' should be accepted.

now let's take L = {a} and parse it to the initial state... As we see clearly, 'a' is not accepted by the given machine M.

Therefore option (B) is correct
None of the options are correct. Let me give counter-examples:-
A) w = 'abbb'. M would accept but L won't.
B) w = 'b'. M won't accept but L would. This example is also applicable to option A and C.
C) w = 'aabb'. M won't accept but L would.
D) Same as option B.
Please don't say that 'a' has to be there in w. Then {a,b}* won't have any significance. Because the language produced by {a,b}* = {empty, a, b, aa, bb, aba, baa, ..............}.

1
2