Past exam question: 2081 Chaitra (Regular), Q2(a)(ii)
Open in the Padhaiko appQuestion
Construct DFA that accepts all the string that doesn't contain two consecutive b over and process the string .
Solution
DFA Design for Language with No Consecutive 'b's: The language consists of all strings over that do not contain the substring "bb".
State Formulation:
- : Start state; last symbol was not '' (or initial ). No consecutive ''s observed. (Accept state)
- : Exactly one trailing '' has just been read without forming "bb". (Accept state)
- : Substring "bb" has occurred; permanent dead/trap state. (Reject state)
Transitions:
- From : on , on
- From : on , on
- From : on , on
| State | a | b |
|---|---|---|
| →*q0 | q0 | q1 |
| *q1 | q0 | q2 |
| q2 | q2 | q2 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts a
- ✓ accepts b
- ✓ accepts ab
- ✓ accepts ba
- ✓ accepts aba
- ✓ accepts bab
- ✓ accepts aababa
- ✓ rejects bb
- ✓ rejects abb
- ✓ rejects bba
- ✓ rejects abbb
- ✓ rejects baabb
- ✓ rejects baaababb
Processing and Execution Trace for w = baaababb: We process the given input string of length :
Notice that contains consecutive ''s at its end, so it must be rejected by the DFA.
Trace of state transitions:
Upon reading the final symbol '', the automaton transitions from into trap state . Since , the string is correctly rejected.
Answer:
The 3-state DFA accepts in and , trapping in upon reading "bb". Processing traces , correctly rejecting .