Skip to main content

Illustration Minimal DFA - even number of 0s and 1s

DFA - number of 0's and 1's have the same remainder when divided by 2
Get illustration

Share — copy and redistribute the material in any medium or format

Adapt — remix, transform, and build upon the material for any purpose, even commercially.

Sharing and adapting of the illustration is allowed with indication of the link to the illustration.

Sketch a deterministic finite automaton (DFA) for the following regular language (type 3):$$ L ~=~ \{ w \in {0,1}^* ~:~ |w|_0 \equiv |w|_1 \text{ mod } 2 \} $$

This is an infinite language where \(|w|_0\) (number of 0s in the word \(w\)) and \(|w|_1\) (number of 1s in the word \(w\)) are both either even or odd:$$ L ~=~ \{ \varepsilon, 00, 11, 01, 10, 1111, ~... \} $$