PadhaikoAll subjects

Past exam question: 2082 Chaitra (Regular), Q4

Theory of Computation · 4 marks

Open in the Padhaiko app

Topic: Finite State Machines & DFA Design

Question

Design a DFA over that can recognize the string containing number of 1 multiple of 3 and number of 0 multiple of 2. Check your design for .

Solution

State Representation and Invariant: The condition requires simultaneously tracking:

We define states where and :

Transition Function:

Transition Table and Automaton Specification: The formal transition table for DFA is:

StateInput 0Input 1
DFA: Number of 0s mod 2 = 0 and 1s mod 3 = 0DFA
DFA: Number of 0s mod 2 = 0 and 1s mod 3 = 0 0 1 0 1 0 1 0 1 0 1 0 1 q00 q01 q02 q10 q11 q12
State01
→*q00q10q01
q01q11q02
q02q12q00
q10q00q11
q11q01q12
q12q02q10
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts 00
  • ✓ accepts 111
  • ✓ accepts 00111
  • ✓ accepts 1010111001
  • ✓ accepts 11100
  • ✓ rejects 0
  • ✓ rejects 1
  • ✓ rejects 01
  • ✓ rejects 10
  • ✓ rejects 11
  • ✓ rejects 000
  • ✓ rejects 1010

Verification Trace for Given String w = 1010111001: Given string has length :

Since both modulo constraints are satisfied, must be accepted.

Trace of state transitions:

The final state is , so the string is correctly accepted.

Answer:

The 6-state DFA tracking accepts strings ending in state . For , the machine processes all 10 symbols and terminates in accepting state , confirming that is accepted.

All past exam questions for Theory of Computation