Skip to main content

Illustration DFA - Binary representation of n divisible by 3

<span>DFA - Binary representation of n divisible by 3</span>
DFA - Binary representation of n divisible by 3
Download

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 of a deterministic finite automaton (DEA) for the following regular language (type 3):$$ L ~=~ \{ w \in \{0,1\}^* ~:~ w \text{ is the binary representation of } n \in \mathbb{N} \text{ which is divisible by 3 (possibly with leading 0s)} \} $$

This is an infinite language, with, for example, the following words:$$ L ~=~ \{ \varepsilon, 0, 1001, 1011010, ~... \} $$