The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
1.9k 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$.
asked in Theory of Computation by Veteran (59.5k points)
edited by | 1.9k views

4 Answers

+27 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.3k points)
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 :)
+3
@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 

+1 vote

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

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

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

set2018 

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 . 

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


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

39,848 questions
46,816 answers
141,158 comments
59,070 users