2,187 views
1 votes
1 votes
What will be the number of non-final states in the minimal DFA for the language L = { the set of strings over alphabet (a.b) containing at least three occurrences of 3 consecutive b’s, overlapping permitted}

1 Answer

0 votes
0 votes
DFA for the language L = {the set of strings over the alphabet {a, b} containing at least three occurrences of three consecutive b's, overlapping permitted}
DFA for the language L = {the set of strings over the alphabet {a, b} containing at least three occurrences of three consecutive b's, overlapping permitted} 

For any Finite Automata question, we should always try writing some strings which belongs to the language,  which will give us clear picture about how to proceed on DFA construction.

Some important observations about the above DFA:

  1. The state 4 in the above DFA indicates that we have seen our 1st occurrence of 3 consecutive b’s, state 7 in the above DFA indicates that we have seen our 2nd occurrence of 3 consecutive b’s and state 10 in the above DFA indicates that we have seen our 3rd occurrence of 3 consecutive b’s which is the final state.
  2. If the string is bbbbb, then we go through states 1,2,3,4,7,10. Here, the three occurences of b’s are overlapped.
  3. If the string is bbbabbbb, then we through states 1,2,3,4,5,6,7,10. The states 5 and 6 are used to handle any a’s that break the sequence of 2nd occurrence 3 consecutive b’s.
  4. Similarly, if the string is bbbbabbb, then we through states 1,2,3,4,7,8,9,10. The states 8 and 9 are used to handle any a’s that break the sequence of 3rd occurrence 3 consecutive b’s.
edited by

Related questions

3 votes
3 votes
3 answers
2
Hirak asked May 22, 2019
1,356 views
How many $2$ state DFA’s with the designated initial state can be constructed over the alphabet over the alphabet $\sum = \{a, b\}$ that accept universal language?$4$$1...
3 votes
3 votes
2 answers
3