The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

+30 votes

Best answer

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

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

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

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

**"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)

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

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

+2

yeah i have done mistake..sorry for that..if we make transition for 'a' on state q_{1 }and q_{2} to state q_{0} then i think it will be correct dfa

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 .

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 586
- Exam Queries 572
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,129 questions

53,252 answers

184,785 comments

70,506 users