The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
1.6k 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\}$

asked in Theory of Computation by Veteran (59.6k points)
edited by | 1.6k views
+1
I found b,c,d as correct. which is the most appropriate?
+5
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.
+11
@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

3 Answers

+34 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.

answered by Active (1.4k points)
edited by
+17

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
+6 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
answered by (117 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, ..............}.
answered by (133 points)
Answer:

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

40,749 questions
47,471 answers
145,587 comments
62,234 users