edited by
12,800 views
50 votes
50 votes

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 by

6 Answers

Best answer
71 votes
71 votes

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.

Hence, correct answer is B.

edited by
12 votes
12 votes
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
3 votes
3 votes
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, ..............}.
0 votes
0 votes
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
Answer:

Related questions