The Gateway to Computer Science Excellence
+23 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$.
in Theory of Computation by Veteran (52.2k points)
edited by | 2.5k views

4 Answers

+36 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)$

by Veteran (57k 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)


what would be the corresponding NFA?
Can anyone give Finite state Diagram for binary subtractor..thanks in advance
Does the regular expression $(a + ab + abb)*$ work for this question?
+1 vote


by Active (3.4k 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!
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.

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.
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,382 answers
105,323 users