GATE CSE 1993 | Question: 27

Question

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

Comments

No String has 3 consecutive occurrences of 'b'
                            |
                            | (complement)
                           V
String has 3 consecutive occurrences of 'b'  means " String Contains SubString 'bbb' somewhere in it"

Create DFA for this than complement it
Final state <----> Non final state

---

we can fist find DFA for 3 consecutive b's using that we find the complement by simply changing the final and non final states of the finite automata and we get our required DFA

---

Question is simple but its analysis is interesting

---

Reg exp: $$(\epsilon + b + bb)(a + ab + abb)^*$$

Answer 1

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

Comments

@pritishc

$b$, $bb$ strings are not generated by your regular expression.

---

@pritishc it will generate all strings starting with ‘a’ including epsilon.

---

@pritishc  @raja11sep  this will generate all strings starting with a and has no consecutive 3 b's or more

Answer 2

This is the approach for solving the given question:-

 

 

 

Comments

This approach is slightly better for exam point of view it's straightforward

Answer 3

a^*((ba⁺)+(bba⁺))^*

Comments

b, bb these strings are also part of the language which will not be generated by your regular expression.

Answer 4

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.

Comments

check for string "abbaabba"
it also accepted by dfa.

---

The first DFA will accept all strings containing at least 3 ‘b’ s.

The second DFA will accept all strings containing less than 3 ‘b’ s.

---

babb not accepted here