PadhaikoAll subjects

Past exam question: 2081 Chaitra (Regular), Q2(a)(ii)

Theory of Computation · 3 marks

Open in the Padhaiko app

Topic: Finite State Machines & DFA Design

Question

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:

Transitions:

DFA: No Consecutive bDFA
DFA: No Consecutive b a, b a b a b q0 q1 q2
Stateab
→*q0q0q1
*q1q0q2
q2q2q2
  • 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 .

All past exam questions for Theory of Computation