2.7k 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.7k 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.
+13
@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.

by Active (1.4k points)
edited
+26

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
+2
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.
+1

@srestha

How option B is correct ?

it is not accepting bb

+2
@satbir Actually you are right.

If there is no "a" then every string $\epsilon, b, bb,bbb,...$ must be accepted, i.e., start state should be final too.

You can choose best fitting answer assuming "a" is there.
0
I agree with you, they should clearly mention it
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
by (113 points)
+1 vote
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, ..............}.
by (221 points)
Check option one bye one

A) string abbb also accepted so A fails

C) string aabb containg substring abb but not accepted hence c fails

D) string abba  does not contain aa but string not accepted hence D fails

B) says every a followed by atlest 2 b's i.e

String abb or babb or abbabb, bbabb such all strings accepted by given machine M So option B true
by (61 points)