The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+19 votes
Draw the state transition of a deterministic finite state automaton which accepts all strings from the alphabet $\{a,b\}$, such that no string has $3$ consecutive occurrences of the letter $b$.
asked in Theory of Computation by Veteran (59.8k points)
edited by | 2.1k views

4 Answers

+30 votes
Best answer

Design a DFA that accepts all strings contain $bbb$  

regular expression $(a+b)^*bbb(a+b)^*$

then take complement of DFA such that no string has $3$ consecutive occurrences of the letter $b$.

having regular expression $(a+ba+bba)^*(\epsilon + b+ bb)$

answered by Veteran (55.8k points)
edited by
^ in regular expression is for?
That is epsilon
@Pravenn Sir how did you get regular expression by Arden's THM ?
q0=  ep + q1a + q2a

q1=q0b , q2 = q1b =q0bb.  , put value of q1 and q2 in first. you will get q0 , then find q1 and q2

regular expression = q0 + q1 +q2

can regular expression be:   (a*(b+ ϵ )(b+ ϵ )aa*)* (b+ ϵ )(b+ ϵ )

regular expression (a+ba+bba)*(ϵ+b+bb)

any other easy way to write regular expressions for the given dfa because using  Arden's theorem its difficult and reqires lots of patience if anyone can share easier way to do this whould be helpful :)
@vishal You can use state elimination method to find the regular expression for a given dfa. It is given in peter linz and also many other books.

 Hemant Parihar will u     

pls share state elimination diagram 


"q0=  ep + q1a + q2a " sir if we put the value we will get q0 = ep+q0ba+q0bba => q0 = ep+q0(ba+bba)

so we have r=q+rp as r = qp* than q0 = ep(ba+bba)* = (ba+bba)*

as RE is q0+q1+q2 => q0+q0b+q0bb => q0(ep+b+bb)

so final RE is (ba+bba)* (ep+b+bb) but your ans doesn't  match

i think we the q0 expression will be q0=  ep + q1a + q2a +q0a because we have incoming edge from q0 itself too

then  final RE is (a+ba+bba)* (ep+b+bb)


+1 vote


answered by Active (3.3k points)
–2 votes
Hi! I have one question - what happens if I want only 3 consecutive occurrences of the letter b to be accepted? I mean bbb and aabbbaaabbbb should be okey, but aabbbbab shouldnt. I think something in q3 must be changed, in order to work, but I dont know what. Would be very nice if you could help me :) Thanks!
answered by (7 points)

 BillyFitt this is regular expression for ur query : a*ba*ba*ba*

–3 votes

In this ,firstly make the dfa of the language which accept all strings from the alphabet (a,b) such that all string contain three consecutive occurrence of the letter b ,then make non final state as final state and final state as non final,initial state will remain same then it become the dfa that accept all string not containing three consecutive b's.

answered by Active (4.1k points)
Idea is perfect. But the transitions for 'a' seems wrong. The first DFA accepts ababab rt?

4 stage is a trap state

From state 2, a transition should go to state 1 rt?

yeah i have done mistake..sorry for that..if we make transition for 'a' on state  q1 and q2 to state q0 then i think it will be correct dfa


whts wrong with this dfa ? @Bikram sir i also got same 



From state 2 there must be a transition towards state 1, which is missing in this DFA.

Tht's why it is not correct.


This DFA is for the language accepting strings with less than 3 'b' s . But here they are asking for strings with no 3 consecutive 'b' s . 

See how your DFA even rejecting abaababab just bcoz it has more than 3 'b' s. But acc to the question it should be accepted . Hope this helps .
check for string "abbaabba"
it also accepted by dfa.

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

47,241 questions
51,471 answers
66,755 users