The Gateway to Computer Science Excellence
+29 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\}$

in Theory of Computation by Veteran (52.2k points)
edited by | 2.7k views
I found b,c,d as correct. which is the most appropriate?
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.
@Vikrant: b is the answer assuming start start state is also accepting rt? I guess it was a printing mistake.
It should be aa not just a

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

so C is wrong.

4 Answers

+48 votes
Best answer

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.

by Active (1.4k points)
edited by

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 . 

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)
nice catch praveen sir
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.


How option B is correct ?

it is not accepting bb

@Arjun Sir, please either correct the question or the answer.

@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.
I agree with you, they should clearly mention it
+8 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
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)
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
by (61 points)

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,737 questions
57,321 answers
105,153 users