2.1k views
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$.
edited | 2.1k views

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

edited by
0
^ in regular expression is for?
0
That is epsilon
0
@Pravenn Sir how did you get regular expression by Arden's THM ?
0
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
+1

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

+1
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 :)
+4
@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.
0

Hemant Parihar will u

pls share state elimination diagram

0

"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

a*((ba+)+(bba+))*

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!
0

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

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.

+1
Idea is perfect. But the transitions for 'a' seems wrong. The first DFA accepts ababab rt?
0

4 stage is a trap state

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

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

0

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

0

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

Tht's why it is not correct.

+1

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 .

+1
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 .
0
check for string "abbaabba"
it also accepted by dfa.

1
2