PadhaikoAll subjects

Past exam question: 2082 Kartik (Back), Q2(b)(i)

Theory of Computation · 3 marks

Open in the Padhaiko app

Topic: Finite State Machines & DFA Design

Question

Design a DFA with that accepts all strings containing even number of zero's and odd number of on, s.

Solution

State Definitions and Parity Invariant: The language requires tracking two independent binary parities for strings over :

This yields states:

Transitions:

DFA Transition Table and Automaton Specification: The transition function is tabulated as:

StateInput 0Input 1
DFA: Even 0s and Odd 1sDFA
DFA: Even 0s and Odd 1s 0 1 0 1 0 1 0 1 q_ee q_eo q_oe q_oo
State01
→q_eeq_oeq_eo
*q_eoq_ooq_ee
q_oeq_eeq_oo
q_ooq_eoq_oe
  • Machine-checked
  • ✓ accepts 1
  • ✓ accepts 001
  • ✓ accepts 100
  • ✓ accepts 010
  • ✓ accepts 111
  • ✓ accepts 00111
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 11
  • ✓ rejects 01
  • ✓ rejects 10
  • ✓ rejects 00
  • ✓ rejects 000
  • ✓ rejects 1100
Answer:

A 4-state DFA tracks parities with start state and unique accept state . Each input symbol toggles its corresponding coordinate.

All past exam questions for Theory of Computation